__Introduction__

For an example you may look for a certain page in a book. First you get the page number from the index at the end of the book. Then you randomly open the book and see it's page number. Say you have opened page 250, out of 500 pages and what you really need is page 256. Now it's obvious that the required page is at the latter half of the book.

Lets make this more general to make an algorithm out of it.

Divide the data set into two components.

Compare the last component of the first set, if the required item is greater in value, search in the latter half.

Else search in the first half.

__Pseudo code__

if(start > end)

return -1 // Item not found

mid = ( start + end) / 2

if(array[mid] == key)

return mid

else if(array[mid] > key)

return BinarySearch(array, key, mid + 1, end)

else

return BinarySearch(array, key, start, mid - 1)

__Java Code__

URL https://github.com/anuradhawick/Algorithms