An array hands you any index in a single step, but it can't tell you where a value hides. Hunting for one value in an unsorted billion-element array means checking up to 1,000,000,000 slots. Sort the array first, though, and binary search finds any target in at most 30 comparisons, because every look throws away half of what remains.

Binary Search finds a target value in a sorted array or a range of numbers by repeatedly dividing the search space in half, the way you'd look up a name in a phone book: flip to the middle, then decide if the target is in the first or second half and eliminate half of the possibilities with each step. The phone book picture is off in one detail: a human flips proportionally, opening near the front to find "Avery", while binary search always jumps to the dead center. With every comparison, the search “zooms” in on the target, and halving a billion candidates 30 times leaves exactly one. That halving is what a time complexity of O(log n) describes.

Watch the halving happen on a real array. Search [3, 7, 12, 25, 31, 48, 56] for the 31: with left at index 0 and right at index 6, the middle lands on index 3, where the 25 sits. Too small, so the target must be to its right, and three elements die in one look. The new middle is the 48 at index 5: too big, two more elements gone. One candidate remains, index 4 holds the 31, and the search ends after three comparisons. Now predict before reading the code: how many comparisons does the same function spend finding the 3, the very first element of the array?

def binary_search(nums: list[int], target: int) -> int:
    # Start left and right at both ends of the array
    left, right = 0, len(nums) - 1

    while left <= right:
        # Calculate the mid point
        mid = (left + right) // 2

        # Move left to search higher values
        if nums[mid] < target:
            left = mid + 1
        # Move right to search lower values
        elif nums[mid] > target:
            right = mid - 1
        # Found target at mid
        else:
            return mid

    # Target not found
    return -1

Also three: it checks the 25, then the 7, then the 3. A linear scan would have found that one on its first look. You might conclude binary search wins every race, but what it actually promises is the worst case. No search in a million-element array ever takes more than 20 looks, while a linear scan's bad days cost the full million. Mechanically, if the middle element is less than the target, you move the left pointer to middle + 1, ignoring the left half. If it's greater, you adjust the right pointer to middle - 1. Each step cuts the number of candidates roughly in half, so even massive arrays can be searched quickly.

Binary search isn't just for arrays. You can use it to find answers within any range of numbers or answer space. For example, you might want the smallest container size that fits all your items, or the fastest speed your system can run without overheating. In these cases, instead of searching through an array, you're searching through a range of possible answers. The key is that the answer must be one-directional.

def binary_search_range(low: int, high: int, condition) -> int:
    # Start left and right at the range boundaries
    left, right = low, high

    while left <= right:
        # Calculate the mid point
        mid = (left + right) // 2

        # Check if mid satisfies our condition
        if condition(mid):
            # Move right to find smallest valid value
            right = mid - 1
        else:
            # Move left to find a valid value
            left = mid + 1

    # Return the smallest valid value (depends on problem)
    return left

You pick a candidate value from the answer space and test it. Based on whether it satisfies your condition, you adjust the search boundaries. With each iteration, half of the possible answers are eliminated, which pulls you toward the optimal solution quickly. This approach is especially useful when there's no direct formula and you have to lean on the structure of the problem to guide trial and error.

Binary search quickly narrows down the search space to locate a target value. With a sorted array, we set the left pointer at index 0 and the right pointer at index length - 1. For a range of numbers, we put the pointers at the lower and upper bounds (for instance, 1 and the maximum). The core of the algorithm is a while loop with the condition left <= right, which makes sure the final candidate is still checked even when both pointers meet.

Each step starts by finding the middle position using division. We then check if the middle element is our target value. If it matches, we've found it. If the middle is too small, we move left to middle + 1 to search higher values. If it's too large, we move right to middle - 1 to search lower values. Every step throws away half of the remaining search area.

Add it up and you get O(log n) time in O(1) space, with the while (left <= right) condition quietly handling the edge cases that break most hand-rolled searches.

Binary search problems follow a consistent pattern: a while loop where left <= right. Each step calculates the middle point and makes a decision that eliminates half of the remaining possibilities. Look for problems that mention "sorted arrays", "finding a specific value", or anything that asks you to minimize or maximize a value within a range. The trick is spotting when your problem has a clear way to halve the possibilities at each step.

You can also use binary search when searching through a range of possible answers instead of an array. These problems often ask for the "minimum value that satisfies" or "maximum value that works". The one hard requirement is that the answer space must be monotonic: once a value satisfies your condition, all values after it must also satisfy it. If a certain speed is too slow, then all slower speeds will also be too slow.

Binary search is one of the most useful patterns to have in your toolkit. Here are a few tips for implementing it well and dodging the most common bugs:

Before you start, quiz yourself on two things from this page: why does the loop condition use left <= right instead of left < right, and what property must an answer space have before you can binary search it without an array in sight? If both answers come back quickly, you're ready. Searching a sorted array is only the entry-level use of binary search. The hardest variants binary-search the answer space itself, turning O(n) decision problems into O(log n) ones. Work through these to internalize basic search, rotated arrays, BS on answer space, and the iconic Median of Two Sorted Arrays: