# Binary Search

Information on this page is taken from *The Algorithm Design Manual* by Steven
S. Skiena.

**Binary search** is a fast algorithm for searching in a sorted array. We compare
the key \(q\) to the middle item. If \(q\) is smaller, it must appear in the first
half; if not it must reside in the second half. By repeating this process
recursively on the correct half, we locate the key in \(\lg n\) comparisons.

A disadvantage of binary search is that it requires a sorted array and sorting an array takes \(O(n\log n)\) time. However, if there are many searches to perform, the time taken to sort is not an issue.

Binary search is the power behind twenty questions!

## Implementation

def binary_search(item, array, start=None, end=None): """Precondition: array is sorted""" if start is None or end is None: start, end = 0, len(array) middle_index = (start + end) // 2 if start >= end: return False elif item == array[middle_index]: return True elif item < array[middle_index]: return binary_search(item, array, start, middle_index) else: return binary_search(item, array, middle_index + 1, end)

## Libraries

The `bisect`

module provides binary search functions in
Python. `bisect_left(array, item)`

finds the first element that is not less
than a target value. `bisect_right(array, item)`

finds the first element that
is greater than a target value.

from bisect import bisect_left def binary_search(item, array): index = bisect_left(array, item) return 0 <= index < len(array) and array[index] == item

## Related Algorithms

### Counting Occurrences

Suppose we want to count the number of times a given key \(k\) occurs in a given sorted array. We could use binary search to find the index of an element in the correct block in \(O(\lg n)\) time. Then we sequentially test elements to the left and right until we find one that differs from the key. The difference between the boundaries (plus one) gives the count of the number of occurrences of \(k\). This algorithm runs in \(O(\lg n + s)\), where \(s\) is the number of occurrences of the key.

A fast algorithm results by modifying binary search to search for the
*boundary* of the block containing \(k\), instead of \(k\) itself. We perform
this search twice, for a total time of \(O(\lg n)\), so we can count the
occurrences in logarithmic time regardless of the size of the block.

### One-Sided Binary Search

Suppose we don't know the bounds of our sorted collection. Binary search can
also proceed from a specific position at repeatedly larger intervals (1, 2,
4, 8, 16) until we find a value greater than our key. We now have a window
containing the target and can proceed with binary search. *One-sided binary
search* is most useful whenever we are looking for a key that lies close to
our current position.

### Square and Other Roots

Suppose we are searching for the square root \(r\) of \(n\). Notice that the square root of \(n \leq 1\) must be at least 1 and at most \(n\). Consider the midpoint \(m\) of this interval. How does \(m^2\) compare to \(n\)? If \(n \leq m^2\), then the square root must be greater than \(m\), so the algorithm repeats on a new range of values. This application of binary search identifies the square root within ±1 after only \(\lg n\) rounds. Root-finding algorithms that converge faster are known, but this is simple, robust and applies to other functions.