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:

Sorted Array with Seven Elements
Using Binary Search to Find 6 in a Sorted Array
Figure 1: Using Binary Search to Find 6 in a Sorted Array
Sorted Array with Seven Elements
Figure 2: Sorted Array with Seven Elements
Sorted Array with Fifteen Elements
Figure 3: Sorted Array with Fifteen Elements
Number of elementsMaximum Required Comparisons
11
32
73
154
315
636
\( 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.

1

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

2

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