2.2 Binary Search and Eficiency

Consider We are given the same array of numbers as in the last example:

56    89    96    544  2      366  3333        65    695  1       36    59

Now, Just consider the same array in a sorted version (in ascending order/Descending order) [Ascending in this case!]:

1       2      36    56    59    65    89    96    366  544  695  3333

Now, Let’s consider solving the same problem we did last time, To report if any number is part of an array or 

not, and if it is then at what position, but this time let’s do it with the sorted array instead of the unsorted one.

NOTE: There’s a term you need to know, its ‘iterate’. To iterate means to repeat something for every element of any array or list.

In Linear Search, We used to iterate over the entire array to find out if the particular term is part of the array, 

right?

In Binary Search, since we know that the array/list of numbers is sorted, we try to exploit this to our benefit.

Here’s Binary Search in pseudocode:

1. Goto the Middle of the array

2. See if the middle term is less or more than the term we are searching for. If the middle term is more than the number we are searching for, then that number must be to the left of the middle term, If the middle term is less than the number we are searching for, then that number must be to the right of the middle term.

3. If the middle term is more, then we perform binary search on the left part of the array by repeating the same procedure, by first moving to the middle term and then searching again, if the term is to the right or left. If it’s less, then we do the same for the right part of the array.

So, all we are doing is taking benefit of the sorted property to search in less time-consuming manner.

But, how much less time-consuming?

Lets, look once again at what are you doing, (Suppose that the array in which we search has ‘n’ elements!)

At every step, We are throwing away half of the remaining array.

Hence, The Number of times we actually iterate over something would at most be the same as the power of 2, which is equal to n.

Therefore, We do log₂n operations at most so, our efficiency is O(log₂n).

You may find vizualizations of both Linear Search as well as Binary Search and Compare at : https://goo.gl/Vmj9iV .

NOTE: There are more than a few notations of representing efficiency.

Here’s a piece of code with actual implementation of Binary Search in C++:

#include <iostream>

using namespace std;

int binarySearch(int arr[], int l, int r, int x)

{

  while (l <= r)

  {

    int m = l + (r-l)/2;

    // Check if x is present at mid

    if (arr[m] == x){

        return m; 

    }

    // If x greater, ignore left half 

    if (arr[m] < x) {

        l = m + 1;

    }

    // If x is smaller, ignore right half

    else {

         r = m - 1;

     }

  }

  // if we reach here, then element was not present

  return -1;

}

int main(){

            int n;

            cin>>n;

            int arr[n];

            for(int i = 0;i<n;i++){

                        cin>>arr[i];

            }

            int Tofind;

            cout<<”Enter the Number you’d like to find:”<<endl

            cin>>Tofind;

            int z = binarySearch(arr,0,n-1,Tofind);

            if(z==-1){

                        cout<<”The Number wasn’t found!”

}else{

            cout<<”The Number was found at the following position: ”<<z<<endl;

}

}

Exercise

Try re-implementing Binary Search in C++ yourself without copy-pasting or looking at it!