Binary search is often used together with other algorithms such as insertion sort or data structures.
Many of standard libraries binded with languages provide the way to do binary search. C++'s STL (Standard Template Library) provides algorithm functions[?] lower_bound[?] and upper_bound. Java offers binarySearch methods in Arrays class.
Binary search is a logarithmic algorithm and executes in O(log n). Specifically, 1 + log_{2} N iterations are needed to return an answer. It is a considerably faster than linear search. It can be implemented using recursion or iteration, although in many languages it is more elegantly expressed recursively.
This sample Ruby implementation returns true if at least one of the elements of array is equal to value, otherwise return false
def binary_search(array,value) first=0 last=array.size  1 while (first <= last) mid = (first + last) / 2 if (value > array[mid]) first = mid + 1 elsif (value < array[mid]) last = mid  1 else return true end end return false end
An example of binary search in action is a simple guessing game in which a player has to guess a positive integer selected by another player between 1 and N, using only questions answered with yes or no. Supposing N is 16 and the number 11 is selected, the game might proceed as follows.
Is the number greater than 8? (Yes)
Is the number greater than 12? (No)
Is the number greater than 10? (Yes)
Is the number greater than 11? (No)
Therefore, the number must be 11. At most ceiling(log_{2} N) questions are required to determine the number, since each question halves the search space. Note that one less question (iteration) is required than for the general algorithm, since the number is constrained to a particular range.
If N is unknown or infinite, we can still find the mysterious number k in at most <math>2\lceil \log_2k \rceil</math> steps by first computing an N which is larger than or equal to k:
def find_N(array,value) N=1 while (value>array[N1]) N=N*2 end return N end
In the guessing game example, the game would be:
Is the number greater than 1? (Yes)
Is the number greater than 2? (Yes)
Is the number greater than 4? (Yes)
Is the number greater than 8? (Yes)
Is the number greater than 16? (No, N=16, proceed as above)
Is the number greater than 8? (Yes)
Is the number greater than 12? (No)
Is the number greater than 10? (Yes)
Is the number greater than 11? (No)
Also observe that we do not need to ask about 8 twice.
Search Encyclopedia

Featured Article
