Binary search

Today I want to discuss about the binary search algorithm.

Binary search algorithm is generally used for searching a key in a sorted list.

There are three different variation of this algorithm available. In this algorithm I would be explaining the first variation.

The pseudo code of this algorithm would look like


BinarySearch (Array[0..N-1], key)
{
low = 0
high = N-1

while (low <= high) {
mid = (low + high) / 2
if (Array[mid] > key)
high = mid - 1
else if (Array[mid] < key)
low = mid + 1
else
return mid // key present at Array[mid]
}
return -1 // not found
}


The C program would look like



/*
* int binary_search(int array[], int size, int key)
*
* @param array sorted array of integer
* @param size the size of the array
* @param key the search element
*
* @return if search is successful, position of key is returned
* else -1
*
* @desc

int binary_search