Binary Search

Binary Search is a O(log n) algorithm for finding a specific element x in a sorted array of elements. The algorithm repeatedly eliminates half of the array based on a comparison with the middle element.

The problem

Given a sorted array of n elements (integers, strings, etc.) and a search element x. Return the index of x in the array, or -1 if x is not in the array.

In practice we often need to determine if a given element is contained in an array. Consider for example a phone company that sells phone numbers to its customers. The company has an array of all available phone numbers. They can only sell a given number if it is contained in the array. Binary Search is an efficient algorithm to use in such situations.


Note: If you have never seen the algorithm before, check the Algorithm Description section first.

In the first example we successfully find the element we are searching for:

Example of a successful Binary Search

In the next example we search for an element not contained in the array:

Example of an unsuccessful Binary Search

Algorithm Description

Important: The array that we are searching through must be in sorted order for the algorithm to work.

Running Time

At each step of Binary Search, we can eliminate at least half of the search interval. In the worst case, we will eliminate exactly half of the search interval pr. step. We can halve the interval log2(n) times before just one element remains. In the end, we also have to check if the remaining element is the search element. This gives us a maximum of log2(n) + 1 comparisons, which makes Binary Search an O(log n) algorithm.

The table below shows the maximum number of comparisons needed for Binary Search and Linear Search (checking every element one by one).

Max. Comparisons
Array Length Linear Search Binary Search
10 10 4
102 102 7
103 103 10
104 104 14
105 105 17
106 106 20
107 107 24
108 108 27
109 109 30

The plot below shows the difference in running time visually. Note how the gap between Binary Search and Linear Search increases with the size of the array.

Plot of running time for Linear Search and Binary Search