Binary Search Field Notes

0Why binary search exists

Binary search is an efficient way to search for an element in a sorted array. You are given an array and a target (the value you look for). The word sorted is the whole trick: because the values are in order, one comparison at the middle tells you which half the target can be in, and the other half can be dropped without looking at it.

NeetCode calls the set of positions the target could still be in the search space. It starts as the whole array and is cut in half at every step. Two variations show up in interviews:

1. Search Array (lesson 14): a sorted array and a target. Decide whether the target is in the array, and where.
2. Search Range (lesson 15): no array. You get a range of numbers and some way to tell "too big / too small / correct", and you search the range itself.

1Search an array (lesson 14)

Three markers: L, mid, R

Set two pointers. L is the left-most index (0) and R is the right-most index (len(arr) - 1). Together they mark the current search space; at the start that is the whole array. NeetCode also calls them low and high, or left and right. Then compute the middle index:

mid = (L + R) // 2, using integer division (throw away the fraction). mid is the index that splits the current subarray into two halves.

Compare arr[mid] with the target. There are exactly three outcomes:

• target > arr[mid]: every value at or left of mid is too small (the array is sorted). Search the right half: L = mid + 1.
• target < arr[mid]: every value at or right of mid is too big. Search the left half: R = mid - 1.
• target == arr[mid]: found. Return mid.

Each step throws away half of what is left. That is the whole algorithm.

arr = [1, 3, 3, 4, 5, 6, 7, 8]      # NeetCode's array in the code block (note the two 3s)

def binarySearch(arr, target):
    L, R = 0, len(arr) - 1          # search space = whole array

    while L <= R:                    # at least one index is still possible
        mid = (L + R) // 2

        if target > arr[mid]:
            L = mid + 1              # drop mid and everything left of it
        elif target < arr[mid]:
            R = mid - 1              # drop mid and everything right of it
        else:
            return mid               # found
    return -1                        # L crossed R: not in the array

Case 1: the target exists. arr = [1,2,3,4,5,6,7,8], target = 5

The walkthrough in the video uses the array [1,2,3,4,5,6,7,8] (no duplicates). Follow L, mid and R for three loop turns.

Case 2: the target does not exist. Same array, target = 9

9 is bigger than everything, so every comparison says "go right" and L keeps moving up. In the end L walks off the right end of the array, out of bounds. In general the search space is used up when L > R; the loop condition L <= R becomes false and we return -1.

Why L <= R and not L < R

Look at turn 3 of case 1 and turn 4 of case 2. Both have L == R: the search space is exactly one cell, and that cell has not been checked yet. With while L < R the loop would skip it. A target that sits in the last remaining cell would be reported as "not found". The smallest example: binarySearch([7], 7) returns -1 with L < R, because the loop body never runs.

Rule: when R = len(arr) - 1 (R is a real index that may hold the answer), the loop is while L <= R. Section 3 shows the other convention, where R = len(arr) and the loop is while L < R. Both are correct; mixing them is the number one binary search bug.

The overflow note: mid = L + (R - L) // 2

NeetCode mentions a better formula for the middle: L + (R - L) // 2. It gives the same number as (L + R) // 2, but it never computes L + R. In languages with fixed-size integers (Java, C++, Go) L + R can exceed the largest 32-bit int (about 2.1 billion) and wrap around to a negative number. This exact bug sat in Java's own library binary search for years; a Google Research blog post famously wrote it up. Python integers grow as large as needed, so (L + R) // 2 cannot overflow here. Interviewers still like to see the safe form, and it costs nothing, so use it.

# same value, no L + R anywhere
mid = L + (R - L) // 2

# Python ints do not overflow; this would be a bug in Java with 32-bit ints
big = 2**31 - 1
(big + big) // 2            # 2147483647 in Python, negative garbage in Java

Time and space: why log n

The same idea as merge sort's split: divide the size in half until you reach size 1. If you start with n cells and halve x times, you have n / 2^x left. The search ends when that equals 1:

1 = n / 2^x  →  2^x = n  →  x = log2(n).

So the number of comparisons is about log2(n), and time is O(log n). The iterative version keeps only L, R and mid, so space is O(1). (A recursive version costs O(log n) stack frames.)

# the recursive shape, to see the merge-sort-style halving directly
def binary_search_rec(arr, target, L, R):
    if L > R:
        return -1                                   # search space is empty
    mid = L + (R - L) // 2
    if arr[mid] == target:
        return mid
    if target > arr[mid]:
        return binary_search_rec(arr, target, mid + 1, R)
    return binary_search_rec(arr, target, L, mid - 1)

2Search a range (lesson 15)

This is the second variation. You are not given an array. You are given a range of numbers and a way to check a guess. At its core it is still binary search: as long as there is some way to tell whether a guess is too big, too small, or correct, you can adjust the search space in the same way. Often the comparison is done by a predefined function or a math equation instead of arr[mid].

The black box: isCorrect(n)

NeetCode's example is a function isCorrect(n) that returns 1 if n is too big, -1 if too small, and 0 if correct. In the lesson it is hardcoded with 10 as the secret number. In a real problem you do not see the inside; you are given the function as an API (a method you can call but not read) and you treat it as a black box inside your own binary search.

# Return 1 if n is too big, -1 if too small, 0 if correct
def isCorrect(n):
    if n > 10:
        return 1
    elif n < 10:
        return -1
    else:
        return 0

Binary search over the range

Compare with the array version line by line. L and R became low and high, and they are values, not indices. arr[mid] became a call to the black box. Everything else is identical, including the low <= high loop and the mid ± 1 moves.

# Binary search on some range of values
def binarySearch(low, high):

    while low <= high:
        mid = (low + high) // 2

        if isCorrect(mid) > 0:      # mid is too big  → answer is below mid
            high = mid - 1
        elif isCorrect(mid) < 0:    # mid is too small → answer is above mid
            low = mid + 1
        else:
            return mid              # correct
    return -1

binarySearch(1, 100)   # → 10 after 6 guesses

NeetCode warns that these questions can be confusing and subtle: the hard part is figuring out how to modify the typical binary search so that the black box replaces the array comparison. Notice one small trap in the code above: isCorrect(mid) is called twice per turn. That is fine for a cheap function, but if the check is expensive, call it once and store the result.

Time and space

O(log n), where n is the size of the search space (100 here, so at most 7 guesses), not the size of any array. No extra memory is used: O(1) space.

3The three templates

Almost every binary search problem is one of three shapes. Memorize the three as separate templates and do not mix their loop conditions.

Template 1: exact match (while L <= R)

The lesson's version, tidied. Use it when you want one index holding the target and -1 otherwise. R is a real index. Both pointers skip past mid.

def exact_match(nums, target):
    L, R = 0, len(nums) - 1
    while L <= R:
        mid = L + (R - L) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            L = mid + 1
        else:
            R = mid - 1
    return -1

Template 2: boundary, also called lower bound or "first True" (while L < R)

Many problems do not ask "is the target here?" but "where does the answer start?": the first index with value ≥ target, the first bad version, the first speed that is fast enough. Picture the array as answers to a yes/no question. Because the data is sorted, the answers look like F F F T T T: all False, then all True. The word for that is monotonic (it never goes back from True to False). The boundary template finds the first True.

Three things change compared to template 1:

• R = len(nums), one past the end. That lets "no True at all" be a valid answer (len(nums)).
• When mid is True, do R = mid, not mid - 1. mid might be the first True, so keep it.
• Loop while L < R. The loop ends when they meet, and the meeting point is the answer. There is no return -1 inside.

def lower_bound(nums, target):
    """First index i with nums[i] >= target. Returns len(nums) if none."""
    L, R = 0, len(nums)            # R is one past the end
    while L < R:
        mid = L + (R - L) // 2
        if nums[mid] < target:
            L = mid + 1            # mid is too small: answer is to the right
        else:
            R = mid                # mid could be the answer: keep it
    return L                       # L == R here

def upper_bound(nums, target):
    """First index i with nums[i] > target."""
    L, R = 0, len(nums)
    while L < R:
        mid = L + (R - L) // 2
        if nums[mid] <= target:
            L = mid + 1
        else:
            R = mid
    return L

# the same template with any yes/no check
def first_true(n, is_true):
    """Smallest i in [0, n) with is_true(i) True, given F..F T..T. Returns n if none."""
    L, R = 0, n
    while L < R:
        mid = L + (R - L) // 2
        if is_true(mid):
            R = mid
        else:
            L = mid + 1
    return L

Template 3: binary search on the answer

This is lesson 15 in interview clothing. The question asks for a number (a speed, a capacity, a number of days), and checking whether a given number works is easy. Then:

1. Write the check, can(x), that returns True if answer x is good enough. This is your isCorrect.
2. Make sure it is monotonic: if x works, every bigger x works too (or every smaller, depending on the problem). Then the answers look like F F F T T T over the range.
3. Set L and R to the smallest and largest possible answers.
4. Run the boundary template to find the first True. That is the minimum answer.

Example, Koko Eating Bananas (LeetCode 875): piles [3, 6, 7, 11], h = 8 hours. Koko eats k bananas per hour, one pile per hour, and finishes a pile of size p in ceil(p / k) hours. Find the smallest k that finishes in time.

def min_eating_speed(piles, h):
    def can_finish(k):                       # the "isCorrect" black box
        hours = 0
        for p in piles:
            hours += (p + k - 1) // k        # ceil(p / k) with integers
        return hours <= h

    L, R = 1, max(piles)                     # answer space: speeds 1..max pile
    while L < R:
        mid = L + (R - L) // 2
        if can_finish(mid):
            R = mid                          # mid works: try slower
        else:
            L = mid + 1                      # too slow: need faster
    return L

min_eating_speed([3, 6, 7, 11], 8)   # → 4

The mirror image is "largest x that still works" (last True). Sqrt(x) (LeetCode 69) wants the largest k with k * k <= x. With the L <= R template, R ends up sitting on the last value that passed:

def my_sqrt(x):
    L, R = 0, x
    while L <= R:
        mid = L + (R - L) // 2
        if mid * mid <= x:
            L = mid + 1                       # mid fits: look for a bigger one
        else:
            R = mid - 1
    return R                                  # R stops on the last mid that fit

my_sqrt(8)    # → 2   (2*2 = 4 ≤ 8, 3*3 = 9 > 8)

Python's bisect module

Templates 1 and 2 are built into the standard library. bisect_left is exactly lower_bound; bisect_right is exactly upper_bound; insort finds the spot with binary search and inserts there (the insert itself shifts elements, so it is O(n)). In an interview, say "I would use bisect in production" and then still write the loop by hand, because that is what is being tested.

import bisect

a = [1, 2, 2, 2, 5]
bisect.bisect_left(a, 2)     # 1   first index with a[i] >= 2  (= lower_bound)
bisect.bisect_right(a, 2)    # 4   first index with a[i] > 2   (= upper_bound)
bisect.bisect_left(a, 3)     # 4   where 3 would go
bisect.bisect_left(a, 9)     # 5   == len(a): bigger than everything
bisect.insort(a, 3)          # a is now [1, 2, 2, 2, 3, 5]; O(log n) to find, O(n) to shift

# "is target in the sorted list?" with bisect (exact match, template 1)
nums = [1, 2, 3, 4, 5, 6, 7, 8]
i = bisect.bisect_left(nums, 5)
found = i < len(nums) and nums[i] == 5    # True; both checks are needed

4Moves that solve most binary search problems

The lessons teach two variations. Interviews dress them up. These three moves undress them.

Move 1: "Is it monotonic? Then binary search."

Before you write any code, ask one question about the problem: is there a yes/no test that is all False then all True (or all True then all False) across some range? If yes, the boundary lives there, and binary search finds it in O(log n). The range can be array indices, a range of numbers, or version numbers. The test can be nums[i] >= target, isBadVersion(i), or "can I finish with speed k". If the answers flip back and forth (F T F T), binary search is wrong and you need a scan.

First Bad Version (LeetCode 278) is the cleanest example: versions 1..n, a black-box isBadVersion(v), and once a version is bad every later one is bad. That is F F F T T T over 1..n.

def first_bad_version(n, isBadVersion):
    L, R = 1, n                     # answer is guaranteed to exist, so R = n is enough
    while L < R:
        mid = L + (R - L) // 2
        if isBadVersion(mid):
            R = mid                 # mid is bad: it could be the first one
        else:
            L = mid + 1             # mid is good: first bad is after it
    return L

The monotonic test can be less obvious. In Find Minimum in Rotated Sorted Array (LeetCode 153), [4,5,6,7,0,1,2] is not sorted, but the test nums[mid] > nums[R] reads T T T T F F F, and the minimum is the first False.

def find_min_rotated(nums):
    L, R = 0, len(nums) - 1
    while L < R:
        mid = L + (R - L) // 2
        if nums[mid] > nums[R]:
            L = mid + 1                       # mid is in the big part: min is to the right
        else:
            R = mid                           # mid could be the min
    return nums[L]

find_min_rotated([4, 5, 6, 7, 0, 1, 2])   # → 0

Move 2: Search on the answer space

When the question asks "what is the minimum X such that..." or "the maximum X such that...", and X is a number with a clear smallest and largest possible value, do not search the input. Search X.

1. Name the answer variable and its range: L = smallest possible, R = largest possible. For Koko: 1 to max(piles). For "ship packages within D days": max(weights) to sum(weights).
2. Write can(x): a plain loop that says whether answer x is good enough. Usually O(n).
3. Check the direction: does can go from False to True as x grows (minimize) or True to False (maximize)?
4. Run the boundary template. Total time: O(n log(range)).

The template is min_eating_speed in section 3. Copy it and change only can, L, and R.

Move 3: The boundary template for first and last position

Two boundary searches give you the whole run of a value. Find First and Last Position (LeetCode 34): the first index of target is lower_bound(target); the last index is upper_bound(target) - 1. Search Insert Position (LeetCode 35) is lower_bound by itself.

def search_range(nums, target):
    lo = lower_bound(nums, target)              # first i with nums[i] >= target
    if lo == len(nums) or nums[lo] != target:
        return [-1, -1]                        # target is not there at all
    return [lo, upper_bound(nums, target) - 1]  # last i with nums[i] == target

search_range([5, 7, 7, 8, 8, 10], 8)   # → [3, 4]

def search_insert(nums, target):            # LeetCode 35
    return lower_bound(nums, target)

One more disguise: a 2D matrix whose rows are sorted and each row starts after the previous row ends (LeetCode 74) is just a sorted 1D array folded into rows. Binary search on the index 0 .. rows*cols - 1 and translate with row = mid // cols, col = mid % cols.

def search_matrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    L, R = 0, rows * cols - 1
    while L <= R:
        mid = L + (R - L) // 2
        val = matrix[mid // cols][mid % cols]  # unfold the flat index
        if val == target:
            return True
        if val < target:
            L = mid + 1
        else:
            R = mid - 1
    return False

5Big-O summary

In every row, n is the size of the search space: the array length, or the number of possible answers in the range.

* Binary search on unsorted data gives wrong answers, not slow answers. Sorting costs O(n log n), so it pays off only when you will search many times. ** insort finds the position in O(log n), but inserting into a Python list shifts everything after it, which is O(n).

6Mistakes to watch for

L, R = 0, len(arr) - 1
while L < R:        # BUG: skips the case L == R

7Practice, in this order

Solve these on LeetCode with the notes closed. Before each one, say which template you will use and why, then write it.

Your next step today: LeetCode 704. Write it from memory with L <= R, then test it on [1,2,3,4,5,6,7,8] with targets 5 and 9 and compare with the two trace tables above.

8Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.