# 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.

### Examples

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:

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

### Algorithm Description

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

• Set low = 0 and high = n-1 (these are limits of the search interval)
• Repeat the following until x is found, or the search interval is empty:
• Compare x to the middle element, with index mid = ⌊(low + high) / 2⌋
• If x = array[mid]: return mid (x was found at that index)
• If x > array[mid]: set low = mid+1 (x is also greater than every element left of mid)
• If x < array[mid]: set high = mid-1 (x is also smaller than every element right of mid)
• Return -1 (x is not in the array)

### 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.