Binary Search

Introduction:

When we have to check if an element is present in sorted array, we can use this method to check that in \(O(logn)\) time

Problem Statement:

search for an element in an array

Algorithm

1. we have a sorted array of n numbers and a key to search for.

2. we used divide and conquer method here. Divide the array into at "mid"

3. If a[mid] = key return mid

4. If a[mid] < key return search result from left array.

5. If a[mid] > key return search result from right array.

Code :

    #include <bits/stdc++.h>
    using namespace std;
    
    int binary_search(int a[], int low, int high, int key)
    {
        if (high < low)
            return -1;
    
        int mid = (low + high) / 2;
        if (a[mid] == key)
        {
            return mid;
        }
        else if (a[mid] < key)
        {
            return binary_search(a, mid + 1, high, key);
        }
        else
        {
            return binary_search(a, low, mid - 1, key);
        }
    }
    
    int main()
    {
        int n;
        cout << "Enter n: ";
        cin >> n;
    
        int a[n];
    
        for (int i = 0; i << n; i++)
        {
            cin >> a[i];
        }
    
        int key;
        cout << "key: ";
        cin >> key;
        int position = binary_search(a, 0, n - 1, key);
    
        if (position < 0)
        {
            cout << key << " is not found in the list\n";
        }
        else
        {
            cout << key << " occurs at position " << position << " in 0 based indexing\n";
        }
    }

Binary Search

Introduction:

Problem Statement:

Algorithm

Code :

Complexity Analysis :

video resources

web resources

book resources