Maximum in a Bitonic Array

Maximum in a Bitonic Array is a clean lesson in modified binary search. The array is not sorted, yet we can still throw away half of it each step — because its shape tells us which direction the peak lies.

The slow way first

The obvious idea: scan the whole array and track the largest value. That works and is simple, but it is O(n) — it touches every element, ignoring the structure we were handed.

The question to ask: while I am standing on one element, what does my immediate surroundings tell me? If the next element is bigger, I am still climbing and the peak is ahead of me. If the next element is smaller, I have already crested and the peak is behind me (or right here). That single comparison points me toward the peak — exactly what binary search needs.

The idea: let the slope steer you

Keep a window [lo, hi]. Look at the middle mid and compare it with its right neighbour a[mid + 1]:

• If a[mid] < a[mid + 1], we are on the ascending slope. The peak is strictly to the right, so lo = mid + 1.
• Otherwise a[mid] > a[mid + 1], we are on the descending slope. The peak is mid itself or to the left, so hi = mid (we keep mid).

Each step halves the window. When lo and hi meet, they sit on the peak.

The key insight: because the array has exactly one peak, the slope at mid is never ambiguous, and the rising side always contains the peak. That is what makes the halving valid.

Walk through it

Step through the animation. The window [lo, hi] shrinks as discarded cells dim out. At mid = 2 the value 8 is below its neighbour 12, so we are climbing and jump right. At mid = 4 the value 4 is above its neighbour 2, so we are falling and pull hi left. One more compare and lo meets hi on 12 — the peak.

Pseudocode

lo, hi = 0, last index
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] < a[mid + 1]:      # rising slope
        lo = mid + 1             # peak is strictly to the right
    else:                        # falling slope
        hi = mid                 # peak is here or to the left (keep mid)
return a[lo]                      # lo == hi sits on the peak

The Python solution

def find_max(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < a[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return a[lo]

• lo and hi bound the part of the array that might still hold the peak.
• The loop runs while lo < hi (not <=): once they are equal the window is a single cell and we are done.
• mid = (lo + hi) // 2 rounds down, so mid + 1 is always a valid index inside the window — the right-neighbour read never runs off the end.
• Line 5 is the heart of it: a[mid] < a[mid + 1] asks am I still climbing? If yes, the peak is strictly right, so lo = mid + 1.
• Otherwise we keep mid as a candidate with hi = mid — never mid - 1, or we could skip the peak.

Complexity

We use only a couple of index variables, so the extra space is O(1). Halving the window turns the O(n) scan into O(log n) — for a million elements that is about twenty comparisons instead of a million.

When this pattern shows up

Practice