Binary Search is an algorithm that finds a target value in a sorted array or a range of numbers by repeatedly dividing the search space in half. Imagine looking for a specific page in a phone book. Instead of scanning every page, you 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. With every comparison, the search “zooms” in on the target, which gives it a time complexity of O(log n).

Picture finding something in an encyclopedia sorted alphabetically. Instead of reading every page, you open to the center, compare the name on the page with the one you're searching for, and then decide which half of the encyclopedia holds your answer. Binary search on an array works the same way. It uses two pointers: left at the beginning and right at the end. Each iteration calculates the middle index and compares the element there with the target.

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

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. This narrowing process is what makes binary search so efficient. 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 eliminates half of the remaining search area, which is what makes the algorithm so efficient.

This guarantees no candidate is overlooked, even when only one element is left. The while (left <= right) condition is what handles the edge cases, since it keeps checking every candidate until the pointers cross. By halving the search space at each step, the algorithm achieves a time complexity of O(log n) and a constant space complexity of O(1).

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 crucial 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:

Binary search is more than just searching a sorted array. The hardest variants binary-search the answer space itself, turning O(n) decision problems into O(log n) ones. Work through these to internalize the variants — basic search, rotated arrays, BS on answer space, and the iconic Median of Two Sorted Arrays: