Binary Search

Binary Search is the classic way to find something in a sorted array fast. Instead of scanning every element, you keep cutting the search range in half. It is the first "divide and conquer" trick most people learn, and the idea shows up everywhere.

The slow way first

The obvious idea is a linear scan: check every element one by one until you find the target. That works on any array, but it is O(n) — for a million elements you might do a million comparisons.

The key fact we are not using: the array is sorted. When data is sorted, looking at one element tells you which side the target must be on. That lets us throw away half the array with a single comparison.

The idea: halve the range each step

Keep two pointers, lo and hi, marking the part of the array still worth searching. Look at the middle element mid:

• If a[mid] == target, you found it — return mid.
• If a[mid] < target, the target must be to the right, so move lo past mid.
• If a[mid] > target, the target must be to the left, so move hi before mid.

Each step cuts the range roughly in half, so you reach the answer in about log₂(n) steps.

The whole trick is that one comparison removes half of what is left, not just one element.

Walk through it

Step through the animation. We search for 9 in [1, 3, 5, 7, 9, 11]. First mid lands on 5, which is too small, so the entire left half (indices 0, 1, 2) is discarded and dimmed. The next mid lands exactly on 9. Two comparisons find the answer in a six-element array.

Pseudocode

set lo = 0 and hi = last index
while lo <= hi:
    mid = (lo + hi) / 2          # middle of the current range
    if a[mid] == target:
        return mid               # found it
    if a[mid] < target:
        lo = mid + 1             # answer is in the right half
    else:
        hi = mid - 1             # answer is in the left half
return -1                        # range is empty: not found

The Python solution

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

• lo and hi start at the two ends of the array — the full range is in play.
• The loop runs while lo <= hi, meaning there is still at least one element to check.
• mid = (lo + hi) // 2 is the integer midpoint of the current range.
• If a[mid] equals the target, we are done and return mid.
• If a[mid] < target, everything from lo to mid is too small, so we move lo = mid + 1.
• Otherwise a[mid] > target, so the right half is too big and we move hi = mid - 1.
• If the loop ends without a match, lo passed hi — the target is not present, so return -1.

Complexity

Halving the range each step is what turns O(n) into O(log n). A million sorted elements take about 20 comparisons, not a million. And we use only a couple of pointers, so the extra space is O(1).

When this pattern shows up

Practice