বাইনারি সার্চ (Binary Search)

যদি লিস্ট সর্টেড থাকে তবে আমরা আইটেম খুঁজে বের করতে বাইনারি সার্চ টেকনিক ব্যবহার করতে পারি। এই প্রসিডিউরে, পুরো লিস্ট দুটি সাব-লিস্টে ভাগ করা হয়। যদি আইটেম মিডেল পজিশনে পাওয়া যায়, তবে লোকেশন রিটার্ন করে, অন্যথায় বা বাম বা ডান সাব-লিস্টে জাম্প করে একই প্রসেস রিপিট করে যতক্ষণ না আইটেম পাওয়া যায় বা রেঞ্জ অতিক্রম হয়।

বাইনারি সার্চ টেকনিকের কমপ্লেক্সিটি

• টাইম কমপ্লেক্সিটি: বেস্ট কেসে O(1)। এভারেজ বা ওয়ার্স্ট কেসে O(log₂ n)।
• স্পেস কমপ্লেক্সিটি: O(1)

ইনপুট এবং আউটপুট

Input: A sorted list of data: 12 25 48 52 67 79 88 93
The search key 79
Output: Item found at location: 5

অ্যালগরিদম

binarySearch(array, start, end, key)
Input - An sorted array, start and end location, and the search key
Output - location of the key (if found), otherwise wrong location.
Begin
    if start <= end then
        mid := start + (end - start) / 2
        if array[mid] = key then
            return mid location
        if array[mid] > key then
            call binarySearch(array, mid+1, end, key)
        else when array[mid] < key then
            call binarySearch(array, start, mid-1, key)
    else
        return invalid location
End

উদাহরণ

#include 
using namespace std;
int binarySearch(int array[], int start, int end, int key) {
    if(start <= end) {
        int mid = (start + (end - start) / 2); //mid location of the list
        if(array[mid] == key)
            return mid;
        if(array[mid] > key)
            return binarySearch(array, start, mid-1, key);
        return binarySearch(array, mid+1, end, key);
    }
    return -1;
}
int main() {
    int n, searchKey, loc;
    cout << "Enter number of items: ";
    cin >> n;
    int arr[n]; //create an array of size n
    cout << "Enter items: " << endl;
    for(int i = 0; i> arr[i];
    }
    cout << "Enter search key to search in the list: ";
    cin >> searchKey;
    if((loc = binarySearch(arr, 0, n, searchKey)) >= 0)
        cout << "Item found at location: " << loc << endl;
    else
        cout << "Item is not found in the list." << endl;
}

আউটপুট

Enter number of items: 8
Enter items:
12 25 48 52 67 79 88 93
Enter search key to search in the list: 79
Item found at location: 5