Searching

Binary Search

TimeO(log n) SpaceO(1)

Think of a phone book. To find “Martinez,” you don’t start at page 1. You open to the middle, see “Johnson,” and know Martinez must be in the second half. You repeat this halving until you land on the right page.

When to use it: The input is sorted (or can be conceptualized as sorted), and you need to find a specific value or a boundary (first/last occurrence, minimum that satisfies a condition).

Key insight: Each comparison eliminates half the remaining search space, turning a linear scan into a logarithmic one.

Common trap: Off-by-one errors in the left/right boundaries. Be precise about whether your range is [left, right] or [left, right) and stay consistent.

function binarySearch(arr, target):
    left = 0
    right = length(arr) - 1

    while left <= right:
        mid = left + (right - left) / 2    # avoid integer overflow

        if arr[mid] == target:
            return mid                      # found it
        else if arr[mid] < target:
            left = mid + 1                  # target is in right half
        else:
            right = mid - 1                 # target is in left half

    return -1                               # target not found

def binary_search(arr: list[int], target: int) -> int:
    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


def lower_bound(arr: list[int], target: int) -> int:
    """Find the first index where arr[i] >= target."""
    left, right = 0, len(arr)

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

    return left

Problem: You are given a sorted array of integers and a target value. Return the index of the first element that is greater than or equal to the target. If no such element exists, return the length of the array.

How would you approach this?

Answer: This is a binary search problem because the array is sorted and we need to find a boundary (the first position satisfying a condition). Use a left-bound binary search where you shrink right = mid when arr[mid] >= target and expand left = mid + 1 otherwise.

Problem: A conveyor belt has packages with weights given in an array. You need to ship all packages within D days in order. Find the minimum weight capacity of the ship.

How would you approach this?

Answer: This is binary search on the answer. The capacity ranges from max(weights) to sum(weights). For each candidate capacity, simulate the shipping in O(n). Binary search narrows the minimum feasible capacity in O(n log S) where S is the search range.

Time: O(log n) because each iteration cuts the search space in half. After k iterations, the remaining space is n / 2^k. We stop when the space is 1 element, so k = log2(n).

Space: O(1) for the iterative version — only a few pointer variables are used regardless of input size. A recursive version would use O(log n) space for the call stack.