Binary search
In computer science, binary search is a search algorithm for searching a set of sorted data for a particular value. A binary search requires random access to the data being searched. In its most simple form, binary search assumes the data is sorted (usually by a sort algorithm) and takes advantage of that characteristic.
| Table of contents |
|
2 The algorithm 3 Language support 4 Applications to complexity theory |
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.
Even if the number we're guessing can be arbitrarily large, in which case there's no upper bound N, we can still find the number in at most steps by first finding an upper bound by repeated doubling. For example, if the number were 11, we could use the following sequence of guesses to find it:
Examples
Therefore, the number must be 11. At most ceiling(log2 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.
In revision control systems, it is possible to use a binary search to see which user added content to a file. One can find a revision which does not include the content, and do a binary search through the history to see where it appeared. Due to the asymptotic analysis above, this is far quicker than checking every difference. However, most useful revision control systems provide some easier to use function for this purpose such as CVS's annotate.
Binary search operates by examining the value in the center of the list; because the values are sorted, it then knows whether the value occurs before or after the center value, and searches through the correct half in the same way. Here is simple pseudocode which determines the index of a given value in a sorted list a between indexes left and right:
Binary search is a logarithmic algorithm and executes in O(log n) time. Specifically, 1 + log2 N iterations are needed to return an answer. It is considerably faster than a linear search. It can be implemented using recursion or iteration, as shown above, although in many languages it is more elegantly expressed recursively.
Many standard libraries provide a way to do binary search. C++'s STL provides algorithm functions
This sample Ruby implementation returns true if at least one of the elements of array is equal to value, and otherwise returns false:
Even if we don't know a fixed range the number k falls in, we can still determine its value by asking simple yes/no questions of the form "Is k greater than x?" for some number x. As a simple consequence of this, if you can answer the question "Is this integer property k greater than a given value?" in some amount of time then you can find the value of that property in the same amount of time with an added factor of log k. This is called a reduction, and it is because of this kind of reduction that most complexity theorists concentrate on decision problems, algorithms that produce a simple yes/no answer.
For example, suppose we could answer "Does this n x n matrix have determinant larger than k?" in O(n2) time. Then, by using binary search, we could find the (ceiling of the) determinant itself in O(n2log d) time, where d is the determinant; notice that d is not the size of the input, but the size of the output.
The algorithm
binarySearch(a, value, left, right)
if right < left
return not found
mid := floor((left+right)/2)
if a[mid] = value
return mid
else if value < a[mid]
binarySearch(a, value, left, mid-1)
else if value > a[mid]
binarySearch(a, value, mid+1, right)
Because the calls are tail-recursive, this can be rewritten as a loop so that it requires only constant space:binarySearch(a, value, left, right)
while left <= right
mid := floor((left+right)/2)
if a[mid] = value
return mid
else if value < a[mid]
right := mid-1
else if value > a[mid]
left := mid+1
return not found
In both cases, the algorithm terminates because on each recursive call or iteration, the range of indexes right minus left always gets smaller, and so must eventually become negative.Language support
lower_bound and upper_bound. Java offers a binarySearch() method for the class Array.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
Applications to complexity theory