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)
{
	bool ans = false; // assume not found till now
	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;
	}
	// target not found
}

// 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 ....