• Binary Search: Binary Search is a searching algorithm, that can be used in a sorted array by repeatedly dividing the search interval into half with a time complexity of O (log N). 

  • Preferred Condition: We prefer Binary Search while searching from a large dataset as it has a time complexity of O (log n), which means, it is much faster than a usual linear search. The dataset should be sorted. The data must be stored in contiguous memory. And data should not have a complex structure or relationships. 

  • Work Process: Consider an array, arr[ ] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} and the target = 23. 
    • First Step: Initially, the search space is from 0 to 9. Let’s denote the boundary by L and H where L = 0 and H = 9 initially. Now mid of this search space is M = 4. So, compare the target with arr[M]. 
    • Second Step: As arr[4] is less than the target, switch the search space to the right of 16, i.e., [5, 9]. Now L = 5, H = 9 and M becomes 7. Compare target with arr[M]. 
    • Third Step: arr[7] is greater than the target. Shift the search space to the left of M, i.e., [5, 6]. So, now L = 5, H = 6 and M = 6. Compare arr[M] with the target. Here arr[M] and target are the same. So, we have found the target. 

  • Algorithm: The basic steps to perform Binary Search are: 
    • Set the low index to the first element of the array and the high index to the last element. 
    • Set the middle index to the average of the low and high indices. 
    • If, the element at the middle index is the target element, return the middle index. 
    • Else, based on the value of the key to be found and the value of the middle element, decide the next search space. 
      • If the target is less than the element at the middle index, set the high index to (middle_index – 1). 
      • If the target is greater than the element at the middle index, set the low index to (middle_index + 1).

  • Code Snippet:

    #include <iostream>
    using namespace std;
    int binarysearch(int arr[], int key, int n)
    {
        int start = 0;
        int end = n-1;
        int mid = start + (end - start)/2;

        while (start <= end)
        {
            if(arr[mid]== key)
            {
                return mid;
            }
            else if(arr[mid]<= key)
            {
                start = mid + 1;
            }
            else
            {
                end = mid - 1;
            }
            mid = start + (end - start)/2;

        }
        return -1;
    }
    int main ()
    {
        int n = 5;
        int arr[5] = {2,4,6,8,10};
        int key = 6;

        int index = binarysearch(arr,6,5);
        cout<<"the index is "<<index;
    }




  • Code Output: 
PS G:\code\> cd "g:\code\" ; if ($?) { g++ a.cpp -o a } ; if ($?) { .\a }
the index is 2



>> Download the .cpp file (coming soon)