Binary Search

Find the first 2 in [1,2,2,2,5]. A midpoint of 2 is not enough: another 2 lies to its left. First decide which positions cannot be answers, then decide what to retain.

Every version has to respect two rules:

1. The search range must shrink on every iteration. Otherwise the loop never ends.
2. If the answer exists, moving l or r must never throw it away. Unless you are sure mid is not the answer, you cannot exclude mid.

The article goes in this order, and each step adds exactly one idea to the previous one:

When to Use This Pattern

The brute-force approach scans left to right. Each element you look at rules out only itself, so it is O(n). When the array is sorted, one look at the middle tells you how the whole left half or the whole right half compares to target, so you discard half at a time: O(log n).

The key word is "whole." Binary search works because some kind of monotonicity lets the result at one position extend to everything on one side of it. Take nums = [1, 3, 5, 6, 8] with the condition nums[i] >= 5:

Once you see that nums[2] satisfies the condition, you know everything to its right does too. Once you see that nums[1] fails, you know everything to its left fails as well.

Recognition Checklist

• The input is sorted, or rotated / rises then falls so that parts of it are still sorted
• The problem asks for a position: first, last, insert point, closest
• You can write a condition that is monotonic in the index: all False at the front, all True at the back
• The problem asks for "the smallest X that works" or "the largest X that works," and check(X) is monotonic
• The input size or the statement calls for O(log n), or O(n log of the value range)

Before You Code

Before writing code, answer these three questions on paper. Once all three answers are written down, the code is mostly transcription.

1. Search Range: if the answer exists, which range must it be in? Usually [0, n-1]. When searching on the answer, it is the range of values, for example [1, max(piles)]. If the answer can fall outside the range (insert at the end, or not found at all), decide up front what the post-processing returns.
2. Search For What: what exactly are you looking for? Write it as one sentence: "the first index where X holds," "the last index where X holds," or "any index equal to target." Many problems don't look like binary search at first only because this sentence hasn't been written yet.
3. How do l and r move, what is the while condition, and how many candidates are left after the loop? These three are tied together: change one and the other two must change with it (the combination table in Step 2 puts them side by side). The main template in this article is l = mid, r = mid with while l < r - 1, which leaves at most two candidates for a nonempty input. When looking for the first, check l first; when looking for the last, check r first.

Try it on LC 35 Search Insert Position with nums = [1, 3, 5, 6] and target = 5:

• Search Range: [0, n-1]. But when target is larger than every number, the answer is n (insert at the end), so the post-processing must fall back to returning n.
• Search For What: the first index where nums[i] >= target.
• How to move: when nums[mid] >= target, mid may be the answer and can't be dropped, so r = mid. Otherwise mid is definitely not the answer, and l = mid won't lose anything. Use while l < r - 1; after the loop l and r remain. Check l, then r, and return n if neither qualifies.

Step 2 turns this paragraph into code.

First Position of Target (LeetCode 34)

This trace covers only LC34's left-boundary subtask: given a nondecreasing array and target, return its first zero-based index, or -1, in O(log n). The full LC34 answer also includes the last index; the output 1 below is not the complete answer [1,3].

Input: nums = [1, 2, 2, 2, 3], target = 2. Expected: 1.

Invariant: if the answer exists, it stays inside [l, r]. while l < r - 1 means there are at least 3 elements on every entry, so both l = m and r = m shrink the range.

1. Walk it by hand

2. Read the rule off the table

• Every row looks at the middle m of the range [l, r].
• If nums[m] >= target, the answer is at m or to its left, so r moves to m (no -1, or the answer could be thrown away). Otherwise l moves to m.
• Stop when only two adjacent elements are left. For the first position, check l before r; if neither matches, return -1.

3. Turn each row into code

def first_position(nums, target):
    if not nums:
        return -1
    l, r = 0, len(nums) - 1
    while l < r - 1:
        m = (l + r) // 2
        if nums[m] >= target:
            r = m
        else:
            l = m
    if nums[l] == target:
        return l
    return r if nums[r] == target else -1

Core Templates

All five steps use the same approach: answer the three questions first, then use the two rules from the top to check that every update is safe.

Step 1: Classic binary search, return on a hit

Problem: find target in a sorted array with no duplicates. Return any index, or -1 if it is not there (LC 704).

The input is a strictly increasing integer array nums and an integer target. If target is in the array, return its index (0-based); otherwise return -1. Required time: O(log n).

For example, [-1, 0, 3, 5] with target = 3 → 2: the 3 sits at index 2.

LeetCode guarantees a nonempty array. The code below also handles an empty array; that assert only checks the extra behavior.

The three questions:

• Search Range: [0, n-1].
• Search For What: any i with nums[i] == target.
• How to move: return immediately when nums[mid] == target. When nums[mid] < target, mid and everything to its left are ≤ nums[mid], so they are all < target and none can be the answer: l = mid + 1. In the opposite case, nums[mid] > target, use r = mid - 1.

What the range means decides the while condition. Here [l, r] is a closed range, both ends included: it holds "positions not yet checked where the answer could be," r - l + 1 of them. mid has just been checked, so both updates use ±1 to exclude it.

• When l == r, one unchecked position is left and the loop must run once more, so the condition is l <= r, not l < r.
• When l > r (exactly l == r + 1), no position is left, which means target does not exist: return -1.

def binary_search(nums, target):
    l, r = 0, len(nums) - 1         # closed range [l, r]: neither end checked yet
    while l <= r:                   # the closed range still has at least one element
        mid = l + (r - l) // 2      # // is floor division; in Java/C++ this form avoids overflow in l + r
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            l = mid + 1             # mid is already checked; the answer can only be to the right
        else:
            r = mid - 1             # mid is already checked; the answer can only be to the left
    return -1                       # l > r: the range is empty


assert binary_search([-1, 0, 3, 5], 3) == 2   # the example from the statement
assert binary_search([1, 3, 5, 7, 9], 7) == 3
assert binary_search([1, 3, 5, 7, 9], 4) == -1
assert binary_search([5], 5) == 0
assert binary_search([], 5) == -1

// is Python's floor division: 7 // 2 == 3. For nonnegative l and r, l + (r - l) // 2 equals (l + r) // 2. Python integers don't overflow; the form just matches the Java/C++ habit.

nums = [1, 3, 5, 7, 9], target = 7:

How does it stop when target is missing? Same array, target = 4:

Row three is the l == r case. With l < r as the condition, the loop would not run here and index 1 would never be checked. That happens not to matter for 4, but searching for 3 would miss the answer.

Check against the two rules: every iteration moves l right by at least one or r left by at least one, so the range always shrinks. The only things excluded are mid and the numbers on one side of it that are smaller (or larger) than target, so the answer is never thrown away.

Variation: 2D matrix (LC 74)

The input is a nonempty m × n integer matrix matrix and target. Return whether target appears in the matrix (True / False, no coordinates). Required time: O(log(m·n)).

The matrix satisfies two conditions: each row increases from left to right, and each row's first number is larger than the previous row's last number. Sorted rows alone are not enough; the second condition must hold too.

For example, [[1, 3, 5], [7, 9, 11]] with target = 9 → True: 9 is at row 1, column 1.

Think first: Taken together, what do the two conditions say about reading the matrix row after row? Without actually building a 1D array, how do you turn a 1D index idx into a row and a column?

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:     # empty matrix, or an empty first row
        return False
    rows, cols = len(matrix), len(matrix[0])
    l, r = 0, rows * cols - 1           # closed range over the flattened array
    while l <= r:
        mid = l + (r - l) // 2
        v = matrix[mid // cols][mid % cols]   # divide by the number of columns: row, column
        if v == target:
            return True
        if v < target:
            l = mid + 1
        else:
            r = mid - 1
    return False


assert search_matrix([[1, 3, 5], [7, 9, 11]], 9) is True   # the example from the statement
m = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
assert search_matrix(m, 16) is True
assert search_matrix(m, 13) is False
assert search_matrix([[1]], 1) is True

Step 1 recap

• What it solves: in a sorted array without duplicates, whether target is there and where.
• The key line: while l <= r with l = mid + 1 / r = mid - 1. The closed range [l, r] is "positions not yet checked"; once mid is checked it is excluded.
• What the variations change: LC 74 only changes how the value at mid is read: the 1D index becomes (mid // cols, mid % cols). The binary search itself is unchanged.
• Easiest mistake: writing while l < r and skipping the last remaining position; dividing by the row count in the matrix conversion.

Step 1 can only answer "is it there?" When the array has duplicates and the problem wants the first occurrence, you can't return on a hit. That is Step 2.

Step 2: First / last occurrence, don't stop on a hit

Problem: a sorted array may contain duplicates. Return the index of the first occurrence of target, or -1 if not found (the first half of LC 34).

LC 34 takes a nondecreasing integer array nums (duplicates allowed) and target, and returns [index of first occurrence, index of last occurrence], 0-based; if target is absent, it returns [-1, -1]. Required time: O(log n).

For example, [5, 7, 7, 8, 8, 10] with target = 8 → [3, 4]: the two 8s sit at indices 3 and 4.

This section finds the first occurrence (the left boundary); the variation below finds the last occurrence (the right boundary). Together they solve LC 34.

nums = [1, 2, 2, 2, 3], target = 2. In the first iteration mid = 2 and nums[2] == 2. You can't return yet (there may be a 2 further left), and you can't drop mid with r = mid - 1 either (mid may be the first 2). This is exactly the second rule: if you aren't sure mid is not the answer, you can't exclude it.

So split the relationship between mid and target into three cases and ask whether mid can be dropped in each:

The last two rows combine into: when nums[mid] >= target, r = mid.

In the first row mid is definitely not the answer, so why l = mid? In this template, l and r are no longer "positions not yet checked" but "the two endpoints checked after the loop." Leaving a known non-answer on an endpoint does no harm; the post-processing filters it out. With = mid on both sides, writing the code means thinking about one thing only: which side mid falls on.

Now the first rule. With = mid, does the range still shrink every iteration? Look at the case with two elements left: l = 0, r = 1, mid = 0 + (1 - 0) // 2 = 0. Running l = mid leaves l at 0, the range doesn't change, the next mid is 0 again, and the loop never ends. With one element left (l == r), mid == l == r and neither update moves anything.

The fix: enter the loop only with at least three elements. [l, r] holds r - l + 1 elements, so "at least three" means r - l >= 2, i.e. while l < r - 1. Then mid sits strictly between l and r:

• (r - l) // 2 >= 2 // 2 = 1, so mid >= l + 1;
• when r - l >= 2, (r - l) // 2 <= r - l - 1, so mid <= r - 1.

For example, l = 0, r = 2 gives mid = 1; l = 0, r = 3 gives mid = 1. With mid strictly inside, both l = mid and r = mid shrink the range.

How many candidates are left after the loop? Each update leaves [l, mid] or [mid, r], and since mid is strictly inside, either one still has at least two elements. So:

• for an input with at least two elements, the loop ends with r == l + 1: l and r are two adjacent candidates;
• for a single element, the loop never runs and l == r == 0: one candidate;
• for an empty array r = -1, and reading nums[l] afterwards fails, so check for empty at the start.

Check l first for the first occurrence and r first for the last:

def first_occurrence(nums, target):
    if not nums:                    # empty array: reading nums[l] later would be out of bounds
        return -1
    l, r = 0, len(nums) - 1
    while l < r - 1:                # at least three elements, l < mid < r
        mid = l + (r - l) // 2
        if nums[mid] >= target:
            r = mid                 # mid may be the first one; keep it
        else:
            l = mid                 # mid is not the answer; leaving it on an endpoint is harmless
    if nums[l] == target:           # looking for the first: check l first
        return l
    if nums[r] == target:
        return r
    return -1


assert first_occurrence([5, 7, 7, 8, 8, 10], 8) == 3   # the example from the statement
assert first_occurrence([1, 2, 2, 2, 3], 2) == 1
assert first_occurrence([2, 2], 2) == 0
assert first_occurrence([1, 3], 2) == -1
assert first_occurrence([], 2) == -1

nums = [1, 2, 2, 2, 3], target = 2:

Why a hit can't use r = mid - 1. Take [1, 2, 3] with target = 2:

Fix the assumptions before comparing templates. All rows use a closed range and a midpoint rounded down (l + (r - l) // 2, same as (l + r) // 2), with empty input handled first. Each update must keep every possible answer among the retained candidates.

Row one is Step 1; row four is this article's main template. Row three shows that "at least three to enter" does not mean "exactly two on exit": from l = 0, r = 2, mid = 1, and r = mid - 1 makes r = 0, leaving one candidate.

Other combinations can work too, for example l = mid with while l < r, provided mid rounds up (there is an example at the end of Step 5). Derive midpoint rounding, updates, the loop condition and the final check together as one set; don't copy one line from each. From here on the article uses row four.

For the last occurrence

, return the index where target appears last in the sorted array, or -1 if it is absent. This is the second half of LC 34.

For example, [5, 7, 7, 8, 8, 10] with target = 8 → 4; [1, 2, 2, 2, 3] with target = 2 → 3.

Think first: For the first occurrence, nums[mid] == target went to the r side. For the last occurrence, which side should equality go to? After the loop, which of l and r do you check first? In [2, 2], looking for the last 2, what would the wrong order return?

def last_occurrence(nums, target):
    if not nums:
        return -1
    l, r = 0, len(nums) - 1
    while l < r - 1:
        mid = l + (r - l) // 2
        if nums[mid] <= target:
            l = mid                 # mid may be the last one; keep it
        else:
            r = mid
    if nums[r] == target:           # looking for the last: check r first
        return r
    if nums[l] == target:
        return l
    return -1


assert last_occurrence([5, 7, 7, 8, 8, 10], 8) == 4   # the example from the statement
assert last_occurrence([1, 2, 2, 2, 3], 2) == 3
assert last_occurrence([2, 2], 2) == 1
assert last_occurrence([1, 3], 2) == -1

# together they solve LC 34
nums = [5, 7, 7, 8, 8, 10]
assert [first_occurrence(nums, 8), last_occurrence(nums, 8)] == [3, 4]
assert [first_occurrence(nums, 6), last_occurrence(nums, 6)] == [-1, -1]

Same skeleton, new problem: insert position (LC 35)

The input is a nonempty, strictly increasing integer array nums and target. If target is in the array, return its index; otherwise return the index where inserting it would keep the array sorted. Don't actually modify the array. Required time: O(log n).

For example, with [1, 3, 5, 6]: target = 2 → 1, since 2 goes between 1 and 3; target = 7 → 4, since 7 is larger than everything and goes at the end, index n = 4.

Unlike LC 34, there is no "not found" here: an insert position always exists.

Think first: Can "its existing index" and "its insert index" both be described by one sentence of the form "the first index where ... holds"? If neither of the two candidates after the loop qualifies, what does that mean, and what do you return?

def search_insert(nums, target):
    if not nums:
        return 0
    l, r = 0, len(nums) - 1
    while l < r - 1:
        mid = l + (r - l) // 2
        if nums[mid] >= target:
            r = mid
        else:
            l = mid
    if nums[l] >= target:           # looking for the first: check l first
        return l
    if nums[r] >= target:
        return r
    return len(nums)                # every number is smaller than target; insert at the end


assert search_insert([1, 3, 5, 6], 2) == 1   # the example from the statement
assert search_insert([1, 3, 5, 6], 7) == 4   # the example from the statement
assert search_insert([1, 3, 5, 6], 5) == 2
assert search_insert([1, 3, 5, 6], 0) == 0

Step 2 recap

• What it solves: first / last occurrence with duplicates, and "first index where a condition holds" problems such as insert position.
• The key line: while l < r - 1. Entering only with at least three elements keeps mid strictly inside, so both l = mid and r = mid shrink the range.
• What the variations change: for the last occurrence, equality goes to the l side (l = mid when <=) and the post-processing checks r first; insert position swaps == for >= in the post-processing and returns n when neither qualifies.
• Easiest mistake: writing r = mid - 1 or returning on a hit; checking l and r in the wrong order (the last 2 in [2, 2] comes back as 0).

Step 3: The one / k elements closest to target

Problem : in a sorted array, find the index of the element closest to target. On a tie, take the smaller one. (Pro lesson)

One step further: the k closest elements (LC 658)

The input is a nondecreasing integer array arr and integers k and x ( 1 <= k <= len(arr) ). (Pro lesson)

Step 3 recap

What it solves : target may not be in the array; find the one or k values closest to it. (Pro lesson)

Step 4: Build your own F/T condition

The first three steps all compared nums[mid] with target. (Pro lesson)

Example 1: one number is missing

Practice here (original problem) ↗ The input is a sorted array of length n holding n of the n + 1 integers from 1 to n + 1, each at most onc… (Pro lesson)

Example 2: minimum of a rotated array (LC 153)

A strictly increasing array with no duplicates is cut at some position and the two parts are swapped, giving the nonempty input nums . (Pro lesson)

Example 3: find target in a rotated array (LC 33)

The input is a rotated array nums like the one in Example 2 (no duplicates) and target . Return target's index, or -1 if it is absent. (Pro lesson)

Example 4: find target in an array that rises then falls (LC 1095)

The input is a "mountain array": strictly increasing up to a peak, then strictly decreasing, with length at least 3. (Pro lesson)

Example 5: unknown array length (LC 702)

The input is a sorted array with no duplicates, but you don't know its length; (Pro lesson)

Step 4 recap

What it solves : the array isn't fully sorted (a missing number, rotated, rises then falls, unknown length), but you can build a condition t… (Pro lesson)

Step 5: Binary search on the answer

Problem : Koko Eating Bananas ( LC 875 ). There are several piles of bananas. Each hour Koko eats at most k bananas, all from one pile. (Pro lesson)

The other direction: the largest feasible value (LC 69)

Given a nonnegative integer x, return its square root rounded down ( LC 69 ). You may not call a power or square-root function. (Pro lesson)

Same skeleton, different check: smallest ship capacity (LC 1011)

The input is a positive integer array weights (package i weighs weights[i] ) and a number of days days . (Pro lesson)

Step 5 recap

What it solves : the problem asks for "the smallest X that works" or "the largest X that works," and feasibility is monotonic in X. (Pro lesson)

Advanced: k-th smallest of two sorted arrays (LC 4)

Problem : given two sorted arrays a and b, find the k-th smallest of their merge. (Pro lesson)

The five steps together

Step What you look for while How to move After the loop Step 1 Any element equal to target l <= r mid ± 1 Nothing; (Pro lesson)

One Problem, Many Disguises

Disguise (how the problem puts it) Translated to the core problem Step LC 374 Guess Number: you're only told too high or too low guess(mid)… (Pro lesson)

Common Pitfalls

When finding the first, writing a hit as r = mid - 1 , or just return mid . (Pro lesson)

Say It in the Interview

First confirm whether the array has duplicates and what to return when the target isn't found, then say something like: I'll binary search f… (Pro lesson)