Binary Search

Very useful searching algorithm, in every step the number of data, which is going to be sorted will cut into half (fig 1). But keep it in your mind that it works on only sorted data.
Let N be the number of data then,
in worst case the comparison will be done log₂(N) + 1 times. And in case of linear searching, the number of comparison would be N.
For example: if we are going to search a number among a million others, in the worst case scenario, the number of comparison would never be exceeded 20. But in case of linear searching algorithm, the number of comparison would be 1.000.000

Source code :

int binSearch(int a[ ], int low, int high, int key)

{

    if(low < high)

    {

        int mid = (low + high) / 2;

        if(a[mid] == key)

            return mid;

        else if(key < a[mid])

            return binSearch(a, low, mid - 1, key);

        else return binSearch(a, mid+1, high, key);

    }

    else return -1;

}

(fig 1)

 Pic from here.

Let me know if something is bugging you or i made mistakes.
Good luck.