Binary Search

Intuition

Think about looking up a word in a printed dictionary. You never start at page one and read forward. You open somewhere in the middle, glance at the first word on the page, and decide whether your word comes before or after it. One glance throws away half the book. Repeat that a dozen times and you are on the right page. Binary search is exactly that habit turned into an algorithm.

The precondition is what makes the trick legal: the data must be sorted (or, more generally, the question you ask must be monotonic: false, false, false, true, true). If the array were shuffled, looking at the middle element would tell you nothing about where the target lives, and you would be stuck with a linear search that checks every element.

How it works step by step

1. Keep two indices, lo = 0 and hi = n - 1, that bound the part of the array where the target could still be.
2. While lo <= hi, compute the middle index mid = lo + (hi - lo) / 2.
3. If nums[mid] == target, you are done: return mid.
4. If nums[mid] < target, the target can only be to the right, so set lo = mid + 1.
5. Otherwise the target can only be to the left, so set hi = mid - 1.
6. If the loop ends because lo > hi, the range is empty and the target is not present: return -1 (or lo, which is where it would be inserted).

The key invariant: if the target exists, it is always inside `[lo, hi]`. Every update must preserve that, and every iteration must make the range strictly smaller. Those two facts together prove the loop is both correct and terminating.

Dry run

Array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0 to 9), target 23.

Three probes for ten elements. Now try a missing target, say 40: the probes land on 16 (go right), 56 (go left), 23 (go right, lo = 6), then 38 at index 6 (go right, lo = 7). Now lo = 7 > hi = 6, the loop stops, and lo = 7 is exactly the index where 40 would be inserted to keep the array sorted. That leftover lo is a free bonus you will use constantly.

Code

public class BinarySearch {
    /** Returns the index of target in sorted nums, or -1 if absent. */
    public static int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2; // avoids int overflow
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    /** First index i with nums[i] >= target (nums.length if none). */
    public static int lowerBound(int[] nums, int target) {
        int lo = 0, hi = nums.length; // half-open range [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        System.out.println(search(a, 23));     // 5
        System.out.println(search(a, 40));     // -1
        System.out.println(lowerBound(a, 40)); // 7
    }
}

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2  # Python ints never overflow
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


def lower_bound(nums, target):
    """First index i with nums[i] >= target (len(nums) if none)."""
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(a, 23), binary_search(a, 40), lower_bound(a, 40))  # 5 -1 7

In production Python you would reach for the standard bisect module (bisect_left is the same as lower_bound), and in Java for Arrays.binarySearch. Interviewers still expect you to write it by hand, though, because the variants below are not in any library.

Time and space complexity

Each iteration halves the remaining range, so after k steps at most n / 2^k elements are left; that hits 1 when k = log2(n). For n = 1,000,000,000 that is only about 30 comparisons, which is why binary search over the answer space is viable even when the answer can be as large as 10^9.

Edge cases

• Empty array: hi = -1, the loop never runs, return -1.
• Single element: one probe, either a match or an immediate exit.
• Target smaller than every element (insertion point 0) or larger than every element (insertion point n).
• Duplicates: plain binary search returns *some* matching index, not necessarily the first. Use lower bound or upper bound when the position matters.
• Very large indices or values: compute mid without overflow, and use long when the search is over answer values near the int limit.

Common mistakes

• Overflow in mid. (lo + hi) / 2 overflows in Java or C++ when both are near 2^31. Write lo + (hi - lo) / 2.
• Mixing range conventions. If hi = n - 1 (closed range) the loop is while (lo <= hi) and you move hi = mid - 1. If hi = n (half-open) the loop is while (lo < hi) and you move hi = mid. Mixing them gives off-by-one bugs or infinite loops.
• Infinite loop with `lo = mid`. When the range has two elements and you set lo = mid with a floor mid, the range never shrinks. Either use lo = mid + 1 or round mid up.
• Forgetting the sorted precondition. Binary searching an unsorted array silently returns wrong answers; it does not crash.
• Returning the wrong thing after the loop. Decide in advance whether the caller wants -1, lo, or hi, and test with a missing target.

Variations and when to use it

The textbook version finds an exact value, but interviews mostly test the generalised form: find the boundary where a monotonic condition flips from false to true. Lower bound and upper bound find the first element that is at least, or strictly greater than, the target, which together count occurrences in O(log n). Rotated sorted arrays work because at least one half around mid is always sorted. Peak finding works because the slope at mid tells you which side climbs.

The most powerful variant is binary search on the answer. If you can write a function feasible(x) that is false for small x and true for large x (can Koko finish at speed x? can we ship in d days with capacity x?), you binary search over x itself instead of over an array. Reach for binary search whenever you see sorted input, an O(log n) requirement, or a 'minimise the maximum' / 'smallest value such that' phrasing.

Related LeetCode problems

• #704 Binary Search — the exact algorithm above, nothing more.
• #35 Search Insert Position — return lo after the loop instead of -1.
• #34 Find First and Last Position of Element in Sorted Array — run lower bound for target and for target + 1.
• #33 Search in Rotated Sorted Array — at each mid, decide which half is sorted, then check whether the target lies in it.
• #374 Guess Number Higher or Lower — the API answer replaces the comparison with nums[mid].
• #2300 Successful Pairs of Spells and Potions — sort potions once, then lower bound the minimum potion strength for each spell.
• #162 Find Peak Element — compare nums[mid] with nums[mid + 1] and move toward the uphill side.
• #875 Koko Eating Bananas — binary search on eating speed with a feasibility check.

FAQ