Tipping Point & Peak

The boundary searches in the previous note all compare against a target value. Binary search doesn't need one. It needs a question whose answer flips once across the range: false, false, true, true. The index where it flips is the tipping point. A peak is a tipping point too: to its left the array goes up, to its right it goes down. You find it with the l < r loop, which squeezes the range down to a single index.

The idea#

With no target, you compare mid with a neighbor instead. In a mountain array:

If arr[mid + 1] > arr[mid], you are on the rising slope, so the peak is to the right of mid: set l = mid + 1.
Otherwise you are at the peak or on the falling slope, so the peak is at mid or to its left: set r = mid.

mid itself stays in range in the second case, which is why it's r = mid and not mid - 1. The loop stops at l == r, and that index is the answer, so there's no separate "found" variable.

The mountain rule is one case of a more general form called first true: given a predicate that is false then true, if pred(mid): r = mid else: l = mid + 1. When l == r, you're standing on the first true. Peak finding uses the predicate "arr[mid] > arr[mid + 1]" (the slope has turned down).

Why `mid + 1` is safe#

With l < r, mid = (l + r) // 2 is always strictly less than r, so mid + 1 never runs off the end. You don't need bounds checks around mid.

How to spot it#

These cues point to a tipping-point search.

"Find a peak", "mountain array", "bitonic".
"Find the single element" in a sorted array of pairs.
Any yes/no condition that is false up to some index and true from then on.
The answer is an index, and you can decide which side it's on by looking at mid and mid + 1.

Template#

Here is the first-true form as a template. Swap in any predicate that flips once.

pred(i): True from the tipping point onwards
lo, hi = first index, last index
while lo < hi:
    mid = (lo + hi) // 2
    if pred(mid):
        hi = mid              # mid may be the answer: keep it
    else:
        lo = mid + 1          # mid is not: discard it
return lo                     # lo == hi: the first true

For a peak, the predicate is arr[i] > arr[i + 1], as in the idea above. It is never called with the last index, because mid < hi inside the loop. The table traces [0, 2, 5, 4, 1].

`lo`	`hi`	`mid`	`arr[mid] > arr[mid+1]`	Move
0	4	2	5 > 4 ✓	`hi = 2`
0	2	1	2 > 5 ✗	`lo = 2`
2	2			stop: peak at 2

Pitfalls#

The l < r loop is unforgiving: one wrong update and it skips the answer or never ends.

r = mid - 1 in an l < r loop. It can skip the answer, because mid might be the peak.
l = mid instead of mid + 1. With mid = (l + r) // 2, two remaining elements never shrink, so the loop runs forever.
Checking mid - 1 and mid + 1 with bounds guards. Comparing only with mid + 1 is simpler and always in range.
Keeping an extra index variable. In the l < r form the answer is l.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Peak Index in a Mountain Array

Use the first-true template with the predicate arr[i] > arr[i + 1]. The first index where the slope turns down is the peak.

Hint: Find Peak Element

The array has many ups and downs, so the predicate no longer flips only once. The same loop still works. It keeps the array rising into lo and falling out of hi (the edges count as $-\infty$ ), so the range always contains a peak. Any peak is a valid answer.

Hint: Single Element in a Sorted Array

Before the single element, pairs start on even indices; after it, they start on odd ones. Snap mid to an even index, then check nums[mid] == nums[mid + 1]. If they match, the single element is to the right.

Hint: Find in Mountain Array

Find the peak first. Then run an ordinary binary search on the rising half and, if needed, a reversed one on the falling half.

Hint: Find a Peak Element II

Binary search over rows. Take the maximum of the middle row, compare it with the cells above and below in that column, and move toward the larger one. That reduces the 2D problem to the 1D rule, at $O(\text{cols} \cdot \log \text{rows})$ .

Key takeaways#

A tipping point is where a yes/no condition flips; a peak is one example.
l < r with r = mid and l = mid + 1; the loop ends with l on the answer.
Compare mid with mid + 1 instead of a target; it is always in range.
First true is the general template behind boundaries, peaks and search on the answer.
2D peaks reduce to 1D by taking the maximum of the middle row.

Core idea#

Binary search does not need a target value. It needs a question whose answer flips once across the range: false, false, true, true. The flip index is the tipping point. A peak is a tipping point too, and the l < r loop squeezes onto it.

Key points#

Compare mid with a neighbor, not a target.
Mountain: if arr[mid + 1] > arr[mid], set l = mid + 1. Otherwise set r = mid.
r = mid keeps mid, because mid may be the answer.
The loop ends at l == r. That index is the answer, so you need no "found" variable.
With l < r, mid < r, so mid + 1 is always in range.
Find Peak Element: the same loop works with many ups and downs. The edges count as $-\infty$ , so the range always holds a peak.
Single element in a sorted array: pairs start on even indices before it and odd after. Snap mid to even and check nums[mid] == nums[mid + 1].
2D peak: binary search rows. Take the middle row's maximum and move toward the larger neighbor. Cost $O(\text{cols} \cdot \log \text{rows})$ .

Template#

pred(i): True from the tipping point onwards
lo, hi = first index, last index
while lo < hi:
    mid = (lo + hi) // 2
    if pred(mid):
        hi = mid          # mid may be the answer
    else:
        lo = mid + 1      # mid is not
return lo                 # first true
# peak: pred(i) = arr[i] > arr[i + 1]

Pitfalls#

r = mid - 1 in an l < r loop. It can skip the peak.
l = mid instead of mid + 1. Two elements never shrink, so the loop runs forever.
Bounds guards around mid - 1 and mid + 1. Compare only with mid + 1.
An extra index variable. The answer is l.

Say it in an interview#

"Search for the first index where the predicate turns true."
"If the next value is bigger, the peak is to the right. Otherwise it is at mid or to the left."

The idea#

Why mid + 1 is safe#

How to spot it#

Template#

Pitfalls#

Problems in this pattern#

Hints#

Key takeaways#

Core idea#

Key points#

Template#

Pitfalls#

Say it in an interview#

Why `mid + 1` is safe#