In its simplest form, binary search is a method for quickly finding a specific target value in a sorted array. It begins by comparing the target value to the middle element of the array. Because the array is sorted, the comparison allows us to determine one-half of the array in which the target cannot lie. The search continues on the remaining half. By doing this repeatedly, we will eventually be left with a search space consisting of a single element, the target value.

Example

In the example above, we're searching for the target value 4 in the given sorted array.

1. In the first step, we compare the middle element of the array 7 with the target value 4. Since 4 < 7, we can safely eliminate the right half of the array, including 7.
2. Now, we're left with elements 1-4 of the array. Since there are an even number of elements, we could pick element 2 or element 3 as the middle element. Let's say we pick element 2, which has a value of 3. Since 4 > 3, we can safely eliminate the left half of the current array, including 3.
3. We're left with elements 3-4. We could pick element 3 or element 4 as the middle element. Let's say we pick element 4, which has a value of 6. Since 4 < 6, we can safely eliminate everything to the right of 6, including 6.
4. We're only left with element 3. We verify that the value at element 3 is indeed the target value 4.

Video Tutorial

You only need to watch the first 4m:30s, after which the video moves on to a more advanced topic (binary search trees).

This video starts with searching a name in a long contact list. It gives good intuition because that is how we look things up in a printed phone book or dictionary. We simulate binary search ourselves, without knowing its called binary search. It also shows you an implementation and walks through it.

Python implementation

In the below pseudocode, we'll modify the goal of the binary search function slightly. The goal is, return the smallest index such that array[index] >= target.

def binary_search(array, target):    # requirement: array is sorted    # returns the smallest index such that array[index] >= target    # if all values are < target, returns len(array)     low = 0    high = len(array)    while high - low > 1:        mid = (high + low)/2        if array[mid] < target:             low = mid        else:            high = mid    return high  

Run-Time analysis

After each step, the size of the array remaining to be searched is halved. Hence, 2^s \geq n. The run-time of the algorithm is O(\log n).

Powerful extensions of binary search

So far in the tutorial, we have assumed that we're looking for a value in an array. In this section, we'll relax this requirement. Relaxing an algorithms assumptions expands when and how an algorithm can be used.

Monotonic function instead of a Sorted array

Binary search can be applied in situations when we have a monotonic function instead of a sorted array.

Example:

Problem: Given a perfect square S (such as 16129 = 127 * 127) between 1 and 1000000, find its square root (assuming you don't know how to calculate the square root). (Also, note that the square root will always lie between 1 and 1000)

Solution: We know that the square root must lie between 1 and 1000. We can keep halving this interval by taking the middle integer M in that range, and comparing M*M with S. For example, in the first step M = 500, and 500 * 500 = 25000 > 16129, so the new range is 1 to 500. Note that we don't need to compute the squares of all the numbers between 1 and 1000.

Continuous function instead of Discrete function

Further, binary search can also be used to find the correct value when the target is continuous (a real number).

Example:

Problem: Given a number S (such as 10.0 = 3.162 * 3.162) between 1 and 1000000.0, find its square root (Same problem as before, but S is not a perfect square).

Solution: The solution is the same. The only thing is, we need to decide to what accuracy do we need the answer. Suppose we need the answer to be accurate to three decimal places. Then, our stopping criteria is

while (high - low) > 0.001:     mid = (high + low) / 2.0    # do stuff

Note that even if we wanted accuracy to within 15 decimal places (the maximum most programming languages store), we'll still only need about 60 iterations total, since log₂(1000/10^-15) < 60.

Side note: It is shocking that 19 out of 20 tutorials on binary search don't talk about the fact that you don't necessarily need an explicit array to perform binary search.

Further Reading

1. Binary Search – topcoder | Wayback Machine - a more detailed write-up on the above.
2. A bonus video is posted in the discussions below. Having it explained in multiple ways helps when you get stuck.

References

1. Binary Search algorithm | Wikipedia