Binary Search

What is binary search?

Binary search is a way to find a value in sorted data. It compares the target with the value in the middle, discards the half that cannot contain the target, and repeats.

Binary search depends on order. The values must already be sorted.

How does it work?

Suppose we want to find 37 in this sorted list:

3, 8, 14, 19, 25, 31, 37, 42, 49, 55, 63, 71, 82, 90, 97

1. The middle value is 42. Since 37 is smaller, discard 42 and everything to its right.
2. The middle of the remaining range is 19. Since 37 is larger, discard 19 and everything to its left.
3. The next middle value is 31. Since 37 is larger, continue to the right.
4. The next value is 37, so the search is complete.

A linear search might inspect the values one by one. Binary search removes about half of the remaining possibilities after every comparison.

The procedure

Keep two positions: the beginning and end of the range that may still contain the target.

1. Find the middle position.
2. Compare its value with the target.
3. If they are equal, return the middle position.
4. If the target is smaller, move the end just before the middle.
5. If the target is larger, move the beginning just after the middle.
6. Stop when the value is found or the range becomes empty.

binary_search(values, target)
    low = 0
    high = length(values) - 1

    while low <= high
        middle = low + floor((high - low) / 2)

        if values[middle] == target
            return middle

        if values[middle] < target
            low = middle + 1
        else
            high = middle - 1

    return not found

The expression used for middle avoids adding low and high directly. In languages with fixed-size integers, that prevents an overflow when both positions are large.

Why must the data be sorted?

The comparison tells us which half can be discarded only because the values have a known order.

If the middle value is 42 and the target is 37, every value after 42 must also be too large. In an unsorted list, 37 could be anywhere, so discarding half would not be justified.

Sorting has a cost. Binary search is most useful when the data is already sorted or when it will be searched many times.

How fast is it?

Binary search takes O(log n) comparisons in the worst case. Doubling the amount of data adds only about one more comparison.

For example, a sorted collection of one million values needs at most about 20 comparisons because 2^{20} is slightly more than one million.

The iterative form above uses O(1) extra space because it keeps only a few positions.

When is binary search useful?

Use it when:

• the data is sorted;
• values can be reached directly by position, as in an array; and
• you need to search the same collection repeatedly.

A simple linear search may be better for a small or unsorted collection. A hash table may be better for exact key lookups when order does not matter.

Common mistakes

• Searching unsorted data: the result is not reliable.
• Updating the wrong boundary: using middle again instead of middle + 1 or middle - 1 can cause an endless loop.
• Ignoring duplicates: ordinary binary search may return any matching position. Finding the first or last match needs a small variation.
• Using it on a linked list: finding the middle repeatedly is not efficient without direct positional access.

What follows?

Binary search is a small example of a powerful idea: use what is already known about the data to rule out many possibilities at once. The same reasoning appears in lower-bound searches, database indexes and other algorithms.

Disclaimer / AI disclosure: This article was created or revised with assistance from artificial intelligence and reviewed by Ujjwal Singh, who takes responsibility for the published content.