Skip to content
Tutorials Center
My learning

Topics

Lesson 74 of 225 ยท Searching

Binary Search Variants

Binary search variants in Python: lower and upper bound, rotated array, peak, 2D matrix, nearly sorted, fixed point, unbounded and mountain arrays.

Plain binary search answers "is x in the list, and where?". Real problems ask slightly different questions. Where is the first 5? How many 5s are there? Where should I insert 7 to keep the list sorted? What is the smallest value in an array that was rotated? Which element is bigger than both its neighbours? Search a sorted matrix?

All of these are variants of one idea. Once you see that idea, you stop memorising a dozen subtly different loops and write one reliable template. This lesson builds that template, then applies it to six classic problems.

One template: the first position where a condition is true

Think of the list as a row of answers to a yes/no question, where all the "no" answers come first and all the "yes" answers come last:

TEXT
index:      0   1   2   3   4   5   6   7
data:       1   2   5   5   5   8   9  12
x >= 5 ?   no  no yes yes yes yes yes yes
                  ^
                  first "yes" = index 2  (lower bound of 5)

Binary search can find the boundary between "no" and "yes" in O(log n) because the answers are monotonic (once yes, always yes). Write the template with a half-open range [lo, hi), where hi = len(items) means "none are yes":

Python
def first_true(lo: int, hi: int, is_yes) -> int:
    while lo < hi:
        mid = (lo + hi) // 2
        if is_yes(mid):
            hi = mid          # mid could be the answer: keep it
        else:
            lo = mid + 1      # mid is a "no": discard it
    return lo

The invariant: the first "yes" lies in [lo, hi]. When the loop ends, lo == hi, and that is the answer (possibly len(items) if nothing was yes).

Lower bound, upper bound, first and last occurrence

  • Lower bound of x: the first index with items[i] >= x (what bisect_left returns).
  • Upper bound of x: the first index with items[i] > x (what bisect_right returns).

From them:

Question Answer
first occurrence of x lower_bound(x), if items[i] == x
last occurrence of x upper_bound(x) - 1, if it is >= 0 and equals x
count of x upper_bound(x) - lower_bound(x)
insertion position keeping order lower_bound(x)
number of items < x lower_bound(x)
number of items <= x upper_bound(x)
Python Lower bound, upper bound, first, last and count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The comparison >= versus > is the only difference between lower and upper bound. A good habit: say the question out loud ("first index where the item is at least x") and the right operator follows.

Floor and ceiling

The floor of x is the largest item <= x; the ceiling is the smallest item >= x. With the bounds above: the ceiling is items[lower_bound(x)] (if in range), and the floor is items[upper_bound(x) - 1] (if the index is not negative). These power "closest value" and "round to the nearest grid line" problems.

Python Floor and ceiling with bisect

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Search in a rotated sorted array

Problem. A sorted array of distinct numbers was rotated at an unknown pivot, for example [6, 7, 9, 15, 1, 2, 4]. Find a target in O(log n).

Brute force. Linear search, O(n). It ignores the structure.

Key insight. Cut the array at mid. At least one half is always sorted. Check which half is sorted, check whether the target lies inside that sorted half's range, and keep that half or discard it.

TEXT
[6, 7, 9, 15, 1, 2, 4]    target = 2
 lo        mid       hi
left half [6..15] is sorted (6 <= 15); is 2 in [6, 15]? no -> go right
[1, 2, 4]  mid=2, found
Python Rotated sorted array: find a value and the minimum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The minimum finder reveals the rotation count: its index is how many places the array was rotated. For arrays with duplicates, a[lo] == a[mid] == a[hi] makes the sorted half impossible to identify, and the worst case degrades to O(n) (you can only shrink the range by one item).

Peak element

Problem. Find an index i where a[i] is greater than its neighbours (the edges count as negative infinity). Adjacent items are different. The array is not sorted.

Insight. Look at mid and mid + 1. If a[mid] < a[mid + 1], the sequence is rising, so a peak exists on the right (either mid + 1 or something beyond it, because the array must come down by the edge at the latest). Otherwise a peak exists at mid or to its left. Binary search works here because of a guarantee, not because the data is sorted.

Python Find a peak element in O(log n)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If an array has several peaks, the answer depends on the path the search takes, and any valid peak is correct.

Searching a 2D matrix

Case A: each row is sorted, and each row starts above the previous row's last value. Treat the matrix as one sorted list of rows x cols items. Index k maps to row = k // cols, col = k % cols. Then run an ordinary binary search: O(log(rows x cols)).

Case B: each row and each column is sorted, but rows do not chain. Start at the top-right corner. If the value is too big, move left; if too small, move down. Each step removes a row or a column: O(rows + cols). (This is a two-pointer idea, see matrices.)

TEXT
Case B, target 14
 1  4  7 11
 2  5  8 12
 3  6  9 16    start at 11 (top-right): 11 < 14 -> down (12) -> down (16)
10 13 14 17                              16 > 14 -> left (9) ... eventually 14
Python Two ways to search a sorted matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

More problem shapes: nearly sorted, fixed point, endless and mountain arrays

The same invariant, "throw away the half that cannot contain the answer", solves many interview variants. Four more are worth knowing, each with one twist.

Almost-sorted array

Problem. Every item sits at most one position away from where it would be in the sorted array, for example [10, 3, 40, 20, 50, 80, 70]. Find a target in O(log n).

The twist: items[mid] is no longer guaranteed to be bigger than everything on its left, because a neighbour may have swapped with it. So check mid - 1, mid and mid + 1. If none matches and items[mid] > target, the target cannot be at mid + 1 or later, and it cannot be at mid or mid - 1 either, so jump to mid - 2. Symmetrically, go to mid + 2 on the other side.

Fixed point: find i where items[i] == i

Problem. items is a sorted array of distinct integers (negatives allowed). Find an index with items[i] == i.

Look at items[i] - i. Because the integers are distinct and increasing, each step to the right raises items[i] by at least 1, so items[i] - i never decreases. That is a monotonic function, which binary search can handle: if items[mid] < mid, a fixed point can only be to the right; if items[mid] > mid, only to the left. With duplicates allowed this argument breaks, and you need a different strategy.

Sorted data of unknown length

Problem. You can read seq[i], but you do not know the length, and reading past the end fails (here with IndexError). Combine exponential search with a bounded binary search: double the index until the value is at least the target (or the read fails), then binary search between the last two indexes, treating a failed read as "too far right".

Search in a mountain (bitonic) array

Problem. The values strictly increase to a peak and then strictly decrease, such as [1, 3, 8, 12, 9, 5, 2]. Find a target in O(log n).

First find the peak with the same slope test as in the peak element problem (compare a[mid] with a[mid + 1]). Then run an ordinary ascending binary search on the left part and a descending binary search on the right part. Three O(log n) searches add up to O(log n).

Python Four more binary-search problem shapes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The unbounded search found 2,100 (index 700) with only 20 reads of a 1,000-item stream, and the mountain search found both ascending-side and descending-side targets.

Complexity summary

Problem Time Space
lower / upper bound, first / last, count O(log n) O(1)
floor / ceiling O(log n) O(1)
rotated array (distinct values) O(log n) O(1)
rotated array with duplicates O(n) worst case O(1)
peak element O(log n) O(1)
matrix, chained rows O(log(rows x cols)) O(1)
matrix, sorted rows and columns (staircase) O(rows + cols) O(1)
nearly sorted array O(log n) O(1)
fixed point (distinct integers) O(log n) O(1)
unbounded sorted data O(log i) for a target at index i O(1)
mountain array O(log n) O(1)

Common mistakes

  • Using the wrong loop shape. When the answer can be mid itself, use hi = mid with lo < hi; when you test equality and can discard mid, use lo <= hi with mid +/- 1. Mixing the two causes infinite loops.
  • Forgetting the "not found" index. lower_bound may return len(items); check the range before reading items[i].
  • Comparing the wrong half in a rotated array. Use a[lo] <= a[mid] (with <=) to detect a sorted left half, because lo can equal mid.
  • Assuming a peak search needs sorted data. It needs only the neighbour guarantee.
  • Rescanning for count. Counting by walking left and right from a match is O(n) in the worst case; use two bounds for O(log n).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does lower_bound(x) return?

    lower_bound is the first position where items[i] >= x, which is also the insertion point that keeps the list sorted and puts x before existing equal items.
  2. 2. In a sorted list, how do you count occurrences of x in O(log n)?

    upper_bound is just past the last x and lower_bound is at the first x, so their difference is the number of copies.
  3. 3. In a rotated sorted array of distinct values, why can binary search still work?

    Checking whether a[lo] <= a[mid] tells you the left half is sorted; otherwise the right half is. A range check on the sorted half decides where to continue.
  4. 4. In peak-finding, if a[mid] < a[mid + 1], where must a peak exist?

    The values keep rising to the right, and since the array ends, they must stop rising somewhere, which creates a peak.
  5. 5. What is the time complexity of the staircase search from the top-right corner of a matrix with sorted rows and columns?

    Every step discards a whole row or a whole column, so at most rows + cols steps are taken.

Summary

  • Most binary-search problems are "find the first index where a monotonic yes/no condition becomes true".
  • lower_bound (>= x) and upper_bound (> x) give first occurrence, last occurrence, count and insertion position.
  • Rotated array: one half is always sorted; test whether the target is in that half.
  • Peak element works on unsorted data because moving toward the rising side guarantees a peak.
  • Matrices: flatten the index for chained rows (O(log(rows x cols))), or use the staircase walk for sorted rows and columns (O(rows + cols)).
  • Nearly sorted arrays: check mid - 1, mid, mid + 1, then jump two places. Fixed point: items[i] - i is monotonic for distinct integers. Unbounded data: double, then binary search. Mountain arrays: find the peak, then search each side.
  • Pick the loop shape (lo < hi with hi = mid, or lo <= hi with mid +/- 1) deliberately and stay consistent.

Next: Binary Search on the Answer