Binary search

Examples

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)

At most 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.

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 (where k is the (unknown) selected number) 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:

• 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)

The algorithm

The most common application of binary search is to find a specific value in a sorted list. To cast this in the frame of the guessing game above, realize that we are now guessing the index, or numbered place, of the value in the list.

The search begins 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:

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.

Binary search is a logarithmic algorithm and executes in O(log n) time. Specifically, 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.

Language support

Many standard libraries provide a way to do binary search. C provides bsearch in its standard library. C++'s STL provides algorithm functions lower_bound and upper_bound. Java offers a binarySearch() method for the class java.util.Arrays.

Example implementations

C

This is a simple implementation of binary search on an array of integers in C based on the above pseudocode. Because typically C compilers don't optimize tail recursion, an iterative version would be better, but this code is for illustration only.

#include int binarySearch(int* a, int value, int left, int right) { int mid; if (right < left) return -1; /* number not found */ mid = (left+right)/2; if (a[mid] == value) return mid; else if (value < a[mid]) return binarySearch(a, value, left, mid-1); else return binarySearch(a, value, mid+1, right); } int main(int argc, char* argv[]) { int array[] = {1, 3, 7, 42, 85, 89, 90}; int array_len = 7; printf("The index of number 7 is %d (indexing starts at 0)\ ", binarySearch(array, 7, 0, array_len-1)); return 0; }

Common Lisp

(defun binary-search (a value left right) (unless (< right left) (let ((mid (truncate (+ left right) 2))) (cond ((= value (elt a mid)) mid) ((< value (elt a mid)) (binary-search a value left (- mid 1))) ((> value (elt a mid)) (binary-search a value (1+ mid) right)))))) (let* ((array '(1 3 7 42 85 89 90)) (array-len (- (length array) 1))) (format t "The index of number 7 is ~a (indexing starts at 0)~%" (binary-search array 7 0 array-len)))

Applications to complexity theory

For example, suppose we could answer "Does this n x n matrix have determinant larger than k?" in O(n²) time. Then, by using binary search, we could find the (ceiling of the) determinant itself in O(n²log d) time, where d is the determinant; notice that d is not the size of the input, but the size of the output.