Binary Search — Algorithm, Time Complexity & Code

Binary search is a fast way to find a target in a sorted list. You check the middle item, rule out half of the remaining values, and repeat. If the list is not ordered, that logic does not hold.

On an ascending list, the rule is simple: if the middle value is smaller than the target, search right; if it is larger, search left. Because the range keeps shrinking by about half, binary search runs in $O(\log n)$ time.

How binary search works on a sorted list

Use this sorted list:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Suppose the target is $31$.

Start with the full range. The middle value is $24$. Since $31 > 24$, everything to the left of $24$ can be discarded, so the search continues in

$$[31, 39, 45, 52]$$

Now the middle value is $39$. Since $31 < 39$, everything to the right of $39$ can be discarded, so the range becomes

$$[31]$$

Now the middle value is $31$, so the search stops. The useful idea is not just that the target was found. In two comparisons, the candidate range dropped from $9$ values to $1$.

Why binary search is $O(\log n)$

Each comparison removes about half of the remaining candidates. After one step, about $n/2$ items remain. After two steps, about $n/4$ remain. After $k$ steps, the remaining size is about

$$\frac{n}{2^k}$$

The search finishes when that quantity is about $1$, so the number of steps satisfies

$$2^k \approx n$$

Taking $\log_2$ of both sides gives

$$k \approx \log_2 n$$

That is why binary search scales well. A linear search may need up to $n$ checks, but binary search only needs enough checks to keep halving the range.

Binary search code example

Here is a standard iterative version in Python:

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

If nums = [3, 7, 12, 18, 24, 31, 39, 45, 52] and target = 31, the function returns index 5.

The condition still matters here: nums must already be sorted in ascending order for these comparisons to be valid.

Common binary search mistakes

Using binary search on unsorted data

This is the main failure case. If the list is not ordered, seeing that the middle item is too small does not justify throwing away the whole left half.

Updating the bounds incorrectly

If you already checked the middle item and it is not the answer, the next range must exclude that middle position. That is why the updates are mid + 1 or mid - 1, not just mid.

Mixing up value and index

Binary search usually returns either the position of the target or a signal that the target was not found. Do not confuse the array value with the index where it was found.

When binary search is used

Binary search is useful whenever you can search over an ordered range. Common cases include sorted arrays, lookup tables, and problems where you need the first or last value that satisfies a condition.

That last case is often called searching for a boundary. If a condition changes from false to true only once across an ordered range, binary search can often find the change point efficiently.

Try a similar problem

Try your own version with a sorted list of $16$ numbers and trace the left, right, and middle positions by hand. Then try a target that is not in the list and watch how the range becomes empty.