If we are given random array and search for a given element !!
Simple Approach : traversing the array once.

Little modification : Now what if we are given an sorted array , now how can one find the element !!
Simple Approach : Linear search i.e. again by traversing the array elements one by one.

// to check whethear element present or not
bool find_element(int A[],int length,int elem_to_found)
{
for(int i=0;i<length;i++)
if(A[i]==elem_to_found)
ans = true; // element found

return ans;
}


Task : Think what should we have to do in order to find at which index element find in array

Now, think what is use of sorting for searching a element.
Here comes best tool binary search i.e. you dont have to traverse a whole array for searching the element and
here how it works :

Binary search looks for a element_to_be_found by comparing the middle index of array (mid)
If its less than the element_to_be_found then it search in the right half of the array i.e. (from mid till end of array)
otherwise if its greater than element_to_be_found than it searches in the left half i.e. (from 0 till mid of array)

Lets look at the implementation of binary search first move to recursive function :

// lets look at the base cases first ( most imp for recursive function )
// if element_to_be_found is found return
// if low(left) and high(right) goes out of bound then return

binary_search_recur(int A[],int element_to_be_found,int low,int high)
{
// element_to_be_found not present in the array
if(low>high)	return -1;

int mid = (low+high)/2;
// element found at mid position
if(A[mid]==element_to_be_found)	return mid;

// if its greater than the mid element recurse again for left half of array i.e. (low,mid-1)
if(element_to_be_found>A[mid])
binary_search_recur(A,element_to_be_found,low,mid-1)

// else its less than the mid element recurse again for right half of array i.e. (mid+1,high)
else(element_to_be_found>A[mid])
binary_search_recur(A,element_to_be_found,mid+1,high)
}


Now look at the iterative one : ;)

binary_search(int A[],int element_to_be_found)
{
int low = 0, high = size(A);

// search for the whole array

while(low<=high)
{
// find the middle value
mid = (low+high)/2;

// if middle element eequals element_to_be_found return index
if(element_to_be_found==A[mid])
return mid;
// if its less then the middle element then it searches for right half and leave the left half
else if(element_to_be_found<A[mid])
low = mid+1;
// if its greater then the middle element then it searches for left half and leave the right half
else
high = mid-1;
}
}

// seems easy ;)
// we can make fun with binary search with structures, trees, reverse binary search


Complexity :

As in each comparision it uses half of the search space ( leaving left part or leaving right part from middle )
i.e. in each comparision it does like
N -> N/2 -> N/4 ….
i.e. it simply proves it takes (big-o-notation) O(log(N))

Upcoming blog of number theory will be more interesting ,
it will tell the actual power of binary search ;)
Stay Tuned with Coding Blocks ….