L13 · Binary Search I — The Template

Series: LeetCode — From Basics to Interview-Ready · Session 13 / 65 · Phase 1 · Core patterns

Watch first

What this pattern IS

You have a sorted array and want to find where a value is (or where it would go). Scanning left to right is O(n). Binary search exploits the sortedness: look at the middle element; because the array is sorted, that one comparison tells you which half the answer is in, so you throw the other half away. Halving the search space each step gives O(log n) — 20 steps for a million elements, 30 for a billion.

The idea is trivial. The bugs are not. Binary search is notorious for three failure modes:

1. Infinite loops — the range never shrinks because mid lands on a boundary you don't move past.
2. Off-by-one — you return mid, mid − 1, or mid + 1 and can't remember which.
3. Overflow — (low + high) overflows in fixed-width languages (not Python, but interviewers still ask).

The cure is discipline: own exactly one template, with a crisp loop invariant, and reframe every problem as "find the first index where a monotone predicate becomes true." That single boundary-finding form solves search, insert-position, first/last occurrence, and (in L15) search-on-the-answer.

First principles

The templates

Template — the ONE to memorise: first index where predicate is true

def lower_bound(lo, hi, predicate):
    """Return the smallest x in [lo, hi] with predicate(x) == True.
    predicate must be MONOTONE: False...False, True...True.
    Returns hi if predicate is never true in range."""
    while lo < hi:                  # half-open: hi is exclusive of the answer region
        mid = lo + (hi - lo) // 2   # overflow-safe midpoint (matters in C++/Java)
        if predicate(mid):
            hi = mid                # mid might be the answer -> keep it
        else:
            lo = mid + 1            # mid is too small -> discard it
    return lo                       # lo == hi == the boundary

Applying it to plain search / insert position

def search_insert(nums, target):
    # first index i where nums[i] >= target  ->  predicate(i) = nums[i] >= target
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo    # insertion point; nums[lo] == target if present
 
def contains(nums, target):
    i = search_insert(nums, target)
    return i < len(nums) and nums[i] == target

First and last occurrence (from the same template)

import bisect
def first_last(nums, target):
    left = bisect.bisect_left(nums, target)     # first index >= target
    right = bisect.bisect_right(nums, target)   # first index > target
    if left == len(nums) or nums[left] != target:
        return (-1, -1)
    return (left, right - 1)                     # inclusive range of target

bisect_left/bisect_right are the standard library's version of exactly this template — use them when allowed, and know how to write them by hand when not.

Mental model

Memory / mnemonic

Own one template by burning in a four-line shape and a rule couplet.

• The shape: while lo < hi: mid; if pred: hi = mid; else lo = mid+1; return lo. Four lines, always the same. Type it a dozen times until your fingers know it.
• The rule couplet: "True keeps mid, False kills mid." True → hi = mid (mid survives as a candidate); False → lo = mid + 1 (mid is killed).
• The midpoint rhyme: "lo plus half the gap" → lo + (hi - lo) // 2, never (lo + hi) // 2 (overflow).
• The return peg: half-open means the loop ends at lo == hi, and that point is the boundary → "return lo."

One template, memorised cold, beats three templates you half-remember and mix up under pressure.

The trap

What interviewers actually ask

Binary search is asked partly to see if you have a template you trust and partly to test boundary reasoning.

• Binary Search (704) · Easy · Amazon, Microsoft — probes: do you have a clean, bug-free template? Follow-up: return the insert position if absent (35).
• Search Insert Position (35) · Easy · Amazon — probes: lower-bound thinking (first index ≥ target). Follow-up: first index strictly greater (upper bound).
• Find First and Last Position of Element in Sorted Array (34) · Medium · Amazon, Meta — probes: two boundaries (bisect_left and bisect_right) in O(log n). Follow-up: count occurrences = right − left.
• First Bad Version (278) · Easy · Google, Amazon — probes: binary search over a monotone predicate isBadVersion, minimising API calls. Follow-up: the overflow-safe midpoint.
• Sqrt(x) (69) · Easy · Amazon — probes: largest m with m*m ≤ x — binary search on the answer (previews L15). Follow-up: return more decimal places.
• Guess Number Higher or Lower (374) · Easy · Amazon — probes: the raw guessing game with a given oracle. Follow-up: the overflow bug in (lo + hi) // 2.

Universal probe: "is your midpoint overflow-safe, and can you prove your loop terminates?" Have both answers ready.

Worked solutions

1. Binary Search (704)

Plain words: given a sorted array and a target, return its index, or −1 if absent.

Brute force: linear scan, O(n). Insight: use the boundary template to find the first index ≥ target, then check if that slot equals target.

def search(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] >= target:        # predicate: value has reached target
            hi = mid
        else:
            lo = mid + 1
    return lo if lo < len(nums) and nums[lo] == target else -1

Complexity: O(log n) time, O(1) memory. Follow-up — "return insert position if absent" (LC35): just return lo without the equality check.

def searchLast(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:                     # first index where nums[mid] > target
        mid = lo + (hi - lo) // 2
        if nums[mid] > target:
            hi = mid
        else:
            lo = mid + 1
    i = lo - 1                         # step back to the last <= target
    return i if i >= 0 and nums[i] == target else -1

2. Find First and Last Position (34)

Plain words: given a sorted array with possible duplicates and a target, return the first and last indices of the target as [first, last], or [-1, -1].

Insight: the first index is the lower bound (first ≥ target); the last is (upper bound) − 1 (upper bound = first > target). Two runs of the same template.

def searchRange(nums, target):
    def lower(x):                      # first index with nums[i] >= x
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] >= x:
                hi = mid
            else:
                lo = mid + 1
        return lo
    left = lower(target)
    if left == len(nums) or nums[left] != target:
        return [-1, -1]
    right = lower(target + 1) - 1      # (first index > target) - 1
    return [left, right]

Complexity: O(log n) time, O(1) memory. Follow-up — "count occurrences": it's right − left + 1, or lower(target+1) − lower(target) directly.

3. First Bad Version (278)

Plain words: versions 1..n; once a version is bad, all later ones are bad. Given an isBadVersion(v) API, find the first bad version with as few calls as possible.

Insight: the predicate isBadVersion is monotone (False...False, True...True) — exactly the template, with the array replaced by the version range.

def firstBadVersion(n, isBadVersion):
    lo, hi = 1, n                      # answer in [1, n]
    while lo < hi:
        mid = lo + (hi - lo) // 2      # overflow-safe (the whole point of this problem)
        if isBadVersion(mid):
            hi = mid                   # bad -> boundary is here or left
        else:
            lo = mid + 1               # good -> boundary is strictly right
    return lo

Complexity: O(log n) API calls, O(1) memory. Follow-up — "why lo + (hi − lo)//2?": in a fixed-width language lo + hi can overflow near INT_MAX; the subtraction form can't.

Tradeoff

Where this shows up

Binary search underlies the standard-library bisect module and C++ lower_bound/upper_bound, which database and search engines use to locate keys in sorted index pages. Version-control git bisect is literally First Bad Version applied to commits: it binary-searches your history for the commit that introduced a bug, halving the suspect range with each test — the monotone predicate being "is the bug present at this commit."

Checkpoint

Quiz

Practice queue

+7d / +21d mark spaced-repetition anchors.

• Binary Search (704) — Easy · the template · +7d anchor.
• Search Insert Position (35) — Easy · lower bound.
• First Bad Version (278) — Easy · predicate over a range.
• Guess Number Higher or Lower (374) — Easy · the guessing game.
• Find First and Last Position (34) — Medium · two boundaries · +21d anchor.
• Sqrt(x) (69) — Easy · binary search on the answer (previews L15).
• Search a 2D Matrix (74) — Medium · flatten to one index space (previews L14).