Tutorial for binary search |
The general idea of a binary search, is to be able to find the location of a value in a sorted array in Log N time.
The two halves of the array are considered separately. If the value being searched (x) is lies between the max and min elements of the right half, the right half is searched similarly. If it lies between the max and min elements of the left half, the left half is searched similarly. If it satisfies none of these conditions, we return that the value does not exist.
So, at each level, of an array with N elements, in the next layer, the array of N/2 elements is searched.
Time complexity is in the order of : N + N/2 + N/4 + ....... 1
== O(log N)
In case you are interested in the C program implementation and tutorial about the binary search you can click here. Closely related ideas of divide and conquer have been used in creating the binary search tree as well, though care should be taken to not confuse the two.