DSA sheet · Binary Search · Patterns roadmap

Binary Search Patterns Roadmap

This is a concept video, not a single LeetCode problem. The teacher's main message: binary search is not only "find a number in a sorted array". It is a way of throwing away half of the possibilities at every step, using some rule that tells you which half can't hold the answer. That is what turns O(n) work into O(log n).

She then gives a roadmap of 4 patterns that cover most interview questions on binary search: (1) basic binary search, (2) rotated arrays / lower & upper bound, (3) binary search on the answer, (4) binary search on a 2D matrix. Every later page in this notebook belongs to one of these four. Learn to recognise them here, and the later problems become "which pattern is this?"

Every part below follows the same order (adapted for a concept video):
① what it is → ② when to use it → ③ intuition → ④ building the logic from her examples → ⑤ steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · The idea: eliminate half, the template, and the two classic doubts
• Part B · Pattern 1: basic binary search
• Part C · Pattern 2: rotated sorted arrays, lower & upper bound
• Part D · Pattern 3: binary search on the answer (Koko)
• Part E · Pattern 4: binary search on a 2D matrix
• Part F · Revision page

Part 0 · Before starting

Words we will use

• Index: the position of an item in an array. Python counts from 0, so in an array of n items, the indexes go 0, 1, …, n−1.
• Sorted (ascending): every item is at least as big as the one before it, e.g. 2 5 8 12 20.
• Search space: the part of the array (or the range of numbers) where the answer could still be. Binary search keeps making this smaller.
• low / high (the teacher also says left / right): two pointers that mark the two ends of the search space. mid is the index in the middle of them.

Why binary search works at all

Binary search needs one thing: when you stand at mid and look at it, you must be able to say "the answer is surely not on this side". In a sorted array that's easy. If the target is bigger than arr[mid], every item on the left of mid is even smaller, so none of them can be the target. The left half can be thrown away.

More generally, it works whenever there is a yes/no question whose answers look like no no no no yes yes yes (or the opposite) as you move from left to right. That shape is called monotonic: once it switches, it never switches back. A sorted array gives you that shape for the question "is arr[i] >= target?".

low, high, mid, and the safer mid formula

The usual way to find the middle is (low + high) // 2. The teacher prefers mid = low + (high - low) // 2. Both give the same number. The difference is only in how big the numbers get while computing it.

• In Java/C++, an int has a maximum (2³¹ − 1). If low and high are both large, low + high can go past that maximum. The number "wraps around" and becomes negative, so mid becomes garbage. This is called overflow.
• high - low is never bigger than high, so the safer form never builds a number larger than the inputs.
• In Python, ints never overflow: they grow as big as needed. So in Python both forms are safe. We still write the safer form, because interviewers expect it and the habit protects you in other languages.

// in Python is "divide and drop the decimal part" (floor division), e.g. 7 // 2 = 3. That's how mid stays a whole index.

Part A · The idea: eliminate half, the template, and the two classic doubts

1What binary search is, in simple words

Most people describe binary search as "searching in a sorted array". The teacher says that description is too narrow. A better description:

Searching for a value is just the most common use of that idea.

2When to use it: the two signals she asks you to remember

1. You can decide a side from mid. If you stand at the middle and some rule tells you "go left" or "go right", binary search is possible, even if nothing looks sorted.
2. The data is sorted, fully or partly. A fully sorted array is the obvious case. But a partly sorted array (for example a sorted array that was rotated, so it is two sorted pieces) is still a binary search candidate.

3Intuition

Think of a guessing game: "I'm thinking of a number from 1 to 100." If you guess 1, 2, 3, … you may need 100 guesses. If you guess 50 and hear "higher", you've removed 50 numbers with one question. Guess 75, hear "lower", and 25 more are gone. Each question cuts what's left in half. That's binary search: always ask about the middle, so that whatever the answer, half the work disappears.

4Building the logic: the steps and the two classic doubts

The teacher lists the basic steps on a small sorted array of 4 items, where index 1 holds 8.

• Put low at the first index (0) and high at the last index (n − 1 = 3).
• Don't walk through the array item by item. Jump to the middle: (0 + 3) / 2 = 1.5, and we drop the decimal → mid = 1, value 8.
• If the target is 8, mid is the answer. Done in one step.
• If the target is 12: compare 12 with 8. 12 is bigger, and the array is sorted, so 12 can only be on the right of 8. Move low to mid + 1 and keep searching only in the right half. The left half is thrown away.

Doubt 1 from the video: why low + (high - low) // 2?

The teacher's picture: imagine numbers simply stop existing after 100. Let high = 100 and low = 1.

Mathematically both formulas give 50.5. But the first one has to build 101 first, and in her imaginary world 101 can't exist. In Java/C++ the "limit" is 2³¹ − 1, and going past it turns the number negative, so you get a wrong mid index. The safe form subtracts first (making a smaller number), halves it (smaller still), and only then adds low back. She says to remember this point for interviews.

Doubt 2 from the video: while low <= high or while low < high?

She says this is where most coders get confused, and gives a rule of thumb:

5Steps (the core template)

1. low = 0, high = n - 1.
2. While low <= high: compute mid = low + (high - low) // 2.
3. If arr[mid] == target → return mid.
4. If arr[mid] < target → the answer is on the right → low = mid + 1.
5. Else → the answer is on the left → high = mid - 1.
6. If the loop ends, the target isn't there → return −1 (or False).

6Code (Python)

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2   # safe middle
        if arr[mid] == target:
            return mid                  # found it
        elif arr[mid] < target:
            low = mid + 1               # throw away the left half (and mid)
        else:
            high = mid - 1              # throw away the right half (and mid)
    return -1                           # space became empty: not present

7Code line by line

8Dry run

Her 4-item array, target 12:

9Complexity & remember

Each step cuts the search space in half: n → n/2 → n/4 → n/8 → … → 1. How many halvings until 1 item is left? The number k with n / 2^k = 1, i.e. k = log₂ n.

• Time O(log n), space O(1) (just three variables).

Part B · Pattern 1: basic binary search

1What it is

The plain case. You get a sorted array and one value, e.g. 8. Is 8 in the array (and where)? This is exactly the template from Part A, used directly.

2When to use it

• The array is fully sorted.
• You are looking for an exact value, or for a position decided by simple comparisons with the target.

3Intuition

Compare with mid. Smaller → go left. Bigger → go right. Equal → done.

4Problems she lists for practice

5–8Steps, code, line by line, dry run

Identical to Part A, steps 5 to 8. Pattern 1 is the template. The next page (Binary Search Basics) goes through it in full detail.

9Complexity & remember

O(log n) time, O(1) space.

Part C · Pattern 2: rotated sorted arrays, lower & upper bound

1What it is

The teacher groups these together under "lower bound and upper bound". The first example is a rotated sorted array: an array that was sorted, and then some items from the end were moved to the front.

Start from 1 2 3 4 5 6 and rotate it 3 times (each rotation moves the last item to the front):

The result 4 5 6 1 2 3 is "sorted in two parts": 4 5 6 is sorted and 1 2 3 is sorted, both ascending. It's called a k-times rotated sorted array (here k = 3).

2When to use it (her three signals)

1. The array is a rotated sorted array.
2. The sorted array contains duplicates.
3. The question asks for the first occurrence or last occurrence of a value.

3Intuition

A rotated array is not a special kind of binary search. It's normal binary search applied to broken pieces. At each mid, first figure out which half is the properly sorted one. In a sorted half, you can safely ask "is the target inside this range?". Then you know which side to keep.

4Building the logic from her example

Why plain binary search fails

Array 4 5 6 1 2 3, target 1.

Plain binary search compares 1 with 6. 1 is smaller, so it assumes 1 must be on the left and sets high = mid - 1. It then searches 4 5, doesn't find 1, and says "not present". That's wrong: 1 is at index 3, in the right half. The "smaller → go left" rule only holds when the whole array is sorted.

The fix: find the sorted half first

• Is mid in the left sorted piece? If arr[low] <= arr[mid], then everything from low to mid is in increasing order (mid is "above" low), so the left half is sorted. Here 4 ≤ 6 → yes.
• Now use the sorted half: is the target between arr[low] and arr[mid]? If yes, search left. Here: is 1 between 4 and 6? No → so it must be in the right half → low = mid + 1.
• If instead arr[low] > arr[mid], the break is inside the left half, so the right half (mid to high) is the sorted one. Check whether the target is between arr[mid] and arr[high] in the same way.

What "lower bound" and "upper bound" mean (for the duplicates / first-last signals)

The pattern's name comes from these two helper searches on a sorted array:

• lower bound of x = the first index whose value is ≥ x.
• upper bound of x = the first index whose value is > x.

First occurrence of 5 = lower bound = 2. Last occurrence = upper bound − 1 = 4. Count of 5s = 5 − 2 = 3. With duplicates, the basic template might stop at any of the 5s, so to get the first or last one we keep searching after a match. Later pages (First & Last Position, Count Occurrences, Floor & Ceiling) build on this.

5Steps (search in a rotated sorted array, distinct values)

1. low = 0, high = n - 1, loop while low <= high.
2. mid as usual. If arr[mid] == target → return mid.
3. If arr[low] <= arr[mid] (left half sorted): if arr[low] <= target < arr[mid] → high = mid - 1, else low = mid + 1.
4. Else (right half sorted): if arr[mid] < target <= arr[high] → low = mid + 1, else high = mid - 1.
5. Loop ends → return −1.

6Code (Python)

def search_rotated(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        if arr[low] <= arr[mid]:                    # left half is sorted
            if arr[low] <= target < arr[mid]:
                high = mid - 1                      # target is inside the left half
            else:
                low = mid + 1
        else:                                       # right half is sorted
            if arr[mid] < target <= arr[high]:
                low = mid + 1                       # target is inside the right half
            else:
                high = mid - 1
    return -1

def lower_bound(arr, x):          # first index with arr[i] >= x
    low, high = 0, len(arr)       # high = n means "past the end"
    while low < high:             # boundary search
        mid = low + (high - low) // 2
        if arr[mid] >= x:
            high = mid            # mid could be the answer, keep it
        else:
            low = mid + 1
    return low

def upper_bound(arr, x):          # first index with arr[i] > x
    low, high = 0, len(arr)
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] > x:
            high = mid
        else:
            low = mid + 1
    return low

7Code line by line

8Dry run: her example with the fix

4 5 6 1 2 3, target 1:

9Complexity & remember

Still O(log n) time, O(1) space: each step does a constant amount of extra checking and still halves the space. (With many duplicates in a rotated array, arr[low] == arr[mid] can hide which half is sorted. That case is handled later in its own problem.)

Part D · Pattern 3: binary search on the answer (Koko)

LeetCode 875 (solved fully on its own page later)

1What it is

The teacher calls this very, very important for interviews, and the tricky one. Here you do not binary search over the given array. You binary search over the range of possible answers. You pick a candidate answer (say 5), test it, and the result tells you whether to try bigger or smaller candidates next, so you jump around the range (2? 7?) instead of trying every value in order.

2When to use it

• The question asks for the minimum (or maximum) value of something that makes a task possible.
• You can write a function check(answer) that says yes/no: "with this answer, can the task be done?"
• That yes/no is monotonic: if one answer works, every bigger one also works (or every smaller one, depending on the problem).

Practice problems she names: Allocate Books (Allocate Minimum Pages), Koko Eating Bananas, Split Array Largest Sum.

3Intuition with her Koko example

A monkey named Koko has piles of bananas: piles = [6, 5, 3, 4] (each number = bananas in that pile). She must finish all of them within h = 8 hours. She eats at a fixed speed of k bananas per hour, and in one hour she works on only one pile. If a pile has fewer than k left, she finishes it and waits for the rest of that hour. Find the smallest speed k that lets her finish in time.

Hours for one pile at speed k = pile ÷ k rounded up, because a partial hour still costs a whole hour.

4Building the logic from her example

She starts with speed 4: 6 hours, which is within 8, so it's valid. But the question wants the minimum speed, so she tries 3: 7 hours, still valid. Then she tries 2. Working it out gives 10 hours, too slow. So the answer is 3.

Notice what she was doing: the "hours needed" part is just a simple function, and the real search was over speeds, values she picked from a range, not items from the array. That's the whole pattern.

5Steps

1. Write hours(k) = sum of ⌈pile / k⌉ over all piles.
2. low = 1, high = max(piles).
3. While low < high (boundary search): mid; if hours(mid) <= h → high = mid, else low = mid + 1.
4. Return low (the first speed that works).

6Code (Python)

class SolutionBrute:
    def minEatingSpeed(self, piles, h):
        k = 1
        while True:
            total = sum((p + k - 1) // k for p in piles)   # ceil(p / k)
            if total <= h:
                return k                                  # first speed that works
            k += 1

class Solution:
    def minEatingSpeed(self, piles, h):
        def hours(k):
            return sum((p + k - 1) // k for p in piles)   # ceil(p / k)

        low, high = 1, max(piles)        # the answer range
        while low < high:                # boundary search
            mid = low + (high - low) // 2
            if hours(mid) <= h:          # mid works: answer is mid or smaller
                high = mid
            else:                        # mid too slow: answer is bigger
                low = mid + 1
        return low

7Code line by line

8Dry run

piles = [6, 5, 3, 4], h = 8, range [1, 6]:

9Complexity & remember

• Brute force: up to max(piles) speeds × n piles each → O(n · max).
• Binary search: log₂(max) checks × O(n) each → O(n log max) time, O(1) space.

Part E · Pattern 4: binary search on a 2D matrix

1What it is

You get a matrix (a grid of rows and columns) that is sorted along each row and down each column. In her example, each row also starts after the previous row ends. Find a target, say 9.

         col0 col1 col2 col3
  row0     2    3    5    6
  row1     7   9   10   11
  row2    12   15   17   18

2When to use it

When the input is a sorted 2D grid. She says this pattern has several variations (e.g. rows sorted but rows overlapping), which come later with their own problems.

3Intuition

• Brute force: two loops, check every cell. O(rows × cols).
• Binary search: first binary search down a column to find the one row that could hold the target, then binary search inside that row.

How the column tells us the row (her reasoning)

Because the matrix is sorted, the first item of a row (7) is bigger than the last item of the row above (6). So compare the target with the last item of each row:

• Row 0 ends with 6. 9 > 6, so 9 can't be in row 0 (everything in row 0 is ≤ 6). Go to a later row.
• Row 1 ends with 11. 9 ≤ 11, so if 9 is anywhere in the matrix, it's in row 1. If it isn't in row 1, it isn't anywhere.

So we binary search the last column for the first row whose last item is ≥ target. (You could use the first column instead, with the matching condition.) Then we binary search that row.

4Building the logic: why log r + log c = log(r·c)

Searching the column costs log r (r = number of rows). Searching one row costs log c (c = number of columns). Total log r + log c = log(r · c).

She shows this isn't magic: "open up" the rows and lay them end to end:

That's just one sorted array of size r·c = 12. Binary search on it costs log(r·c), the same thing. A flat index k maps back to row = k // c, col = k % c (here 5 → row 1, col 1 ✓).

5Steps

1. Binary search rows 0…r−1 for the first row whose last item is ≥ target. If none, return False.
2. Binary search that row for the target.

6Code (Python)

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    r, c = len(matrix), len(matrix[0])

    # 1) binary search on the last column: first row whose end is >= target
    low, high = 0, r - 1
    row = -1
    while low <= high:
        mid = low + (high - low) // 2
        if matrix[mid][c - 1] >= target:
            row = mid                 # this row could hold it; try an earlier one
            high = mid - 1
        else:
            low = mid + 1
    if row == -1:
        return False                  # target is bigger than everything

    # 2) normal binary search inside that row
    low, high = 0, c - 1
    while low <= high:
        mid = low + (high - low) // 2
        if matrix[row][mid] == target:
            return True
        elif matrix[row][mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

7Code line by line

8Dry run

Target 9.

9Complexity & remember

• Brute force O(r · c). Binary search O(log r + log c) = O(log(r·c)) time, O(1) space.

Part F · Revision page

print(binary_search([3, 8, 12, 15], 12))           # 2
print(search_rotated([4, 5, 6, 1, 2, 3], 1))       # 3
print(lower_bound([1, 2, 5, 5, 5, 9], 5))          # 2
print(upper_bound([1, 2, 5, 5, 5, 9], 5))          # 5
print(Solution().minEatingSpeed([6, 5, 3, 4], 8))  # 3
m = [[2, 3, 5, 6], [7, 9, 10, 11], [12, 15, 17, 18]]
print(search_matrix(m, 9), search_matrix(m, 8))    # True False

Based on this video: How to identify Binary Search patterns