Binary Search: The Algorithm That Cuts Work in Half

The Elegance of Halving

Binary search is one of those algorithms that seems almost magical the first time you understand it. Instead of checking every element one by one — O(n) — you eliminate half the remaining search space with each comparison. The result: O(log n) time.

For a sorted array of one million elements, binary search finds any element in at most 20 comparisons. Linear search could take up to 1,000,000. That's the power of logarithms.

The Core Idea

Binary search works on sorted data. It checks the middle element:

• If the middle equals the target: done.
• If the middle is less than the target: the target must be in the right half. Discard the left.
• If the middle is greater: the target is in the left half. Discard the right.

Repeat on the remaining half until you find the target or run out of elements.

The Classic Implementation

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

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Every line here is deliberate. Let's break down the non-obvious parts.

Why left + (right - left) // 2 instead of (left + right) // 2?

In languages with fixed-size integers (C++, Java), left + right can overflow if both are large. The safer form avoids this. In Python it doesn't matter, but the habit is worth keeping.

Why left <= right (not left < right)?

Consider a single-element array: left = 0, right = 0. With strict less-than, you'd never check that element. With less-than-or-equal, you do.

The Three Off-By-One Traps

Binary search is notorious for subtle bugs. These are the three places people go wrong:

1. mid + 1 vs mid — when moving the left pointer, always do left = mid + 1. If you do left = mid, you can loop forever when left and right are adjacent.

2. mid - 1 vs mid — same principle: right = mid - 1, never right = mid (unless you have a specific reason).

3. Inclusive vs. exclusive bounds — pick one style and stick to it. The most common is both inclusive: [left, right]. Some use [left, right) (exclusive right), but mixing them is a recipe for bugs.

Finding the First / Last Occurrence

Classic binary search stops when it finds the target. But what if there are duplicates and you need the first occurrence?

def first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # keep searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

For last occurrence: when arr[mid] equals target, set result = mid and do left = mid + 1 instead — keep searching right.

Binary Search on the Answer

This is the advanced technique that unlocks a whole category of problems. Instead of searching for a value in an array, you binary search on the answer itself.

The pattern: you have a problem asking "what is the minimum/maximum X such that some condition holds?" If that condition is monotone — true for all values above some threshold, false below — you can binary search on X directly.

Classic example: "You have an array of numbers and D days. What's the minimum capacity needed to ship all packages in D days?"

Instead of trying to figure out the answer directly, binary search on capacity:

• Is capacity C enough to ship everything in D days? (Check with a greedy simulation)
• If yes: try smaller capacities (move right pointer down)
• If no: try larger capacities (move left pointer up)

Other problems that use this pattern:

• Koko Eating Bananas
• Minimum Number of Days to Make M Bouquets
• Find the Smallest Divisor Given a Threshold
• Capacity to Ship Packages Within D Days

Rotated Sorted Arrays

What if the sorted array has been rotated? Example: [4,5,6,7,0,1,2]. Standard binary search won't work directly, but you can still do it in O(log n).

The key insight: after a rotation, at least one half of the array is still sorted. Check which half is sorted, then determine if your target falls in that half. If yes, search there. If no, search the other half.

This problem ("Search in Rotated Sorted Array") is a LeetCode classic and appears frequently in real interviews.

The Mental Checklist

Before applying binary search to any problem, ask yourself:

1. Is the data sorted (or can I sort it)?
2. Can I define a monotone condition ("is this value too small/large")?
3. Am I looking for the exact value, or the first/last occurrence, or the boundary?

Answer these three questions and the implementation almost writes itself. Binary search is one of those algorithms where understanding it deeply — not just memorizing it — lets you recognize it in dozens of disguises.