taylorialcom/ DataStructures

Binary Search

Binary search is a fast way to find something if you know your collection is in sorted order.

Suppose we wish to know whether or not a particular value is stored in an array of integers. Consider the following array:

Figure [seven]: Sorted Array with Seven Elements

Figure [sevenArrows]: Using Binary Search to Find 6 in a Sorted Array

Figure [sevenAllArrows]: Sorted Array with Seven Elements

Figure [fifteen]: Sorted Array with Fifteen Elements

Number of elementsMaximum Required Comparisons
\( 2^n - 1 \)\( n \)
\( n \)\( \log_2 n \)

We get the last line by taking the \( \log_2 \) of both entries in the second to the last line since \( \log_2 (2^n - 1) \approx \log_2 2^n = n \).2

It's worth noting that if the size of the array is between \( 2^{n-1} - 1 \) and \( 2^n - 1 \) it still may take up to \( \log_2 n \). We can more correctly say that the maximum number of comparisons required for an array of size \( n \) is \( \log_2 (n+1) \) rounded up to the nearest integer.


fewer if we find what we are looking for before reaching the end of the array.


As \( n \rightarrow \infty \), \( 2^n - 1 \) and \( 2^n \) are indistinguishable.