Binary Search on a Function (Ternary Search Alternative)

Problem Statement

Given a unimodal function f (strictly increasing then strictly decreasing) over an integer range [lo, hi], find the index of its maximum. This generalises "Find Peak Element" to any function you can evaluate.

Example

Input:  f(i) values = [1, 3, 7, 9, 6, 2]
Output: index 3 (value 9)

Approach (Binary Search on the Slope)

Ternary search is the textbook tool for unimodal functions, but binary search on the slope also works and evaluates f fewer times. Compare f(mid) with f(mid+1): if increasing, the peak is to the right (lo = mid+1); otherwise it is at mid or left (hi = mid).

Complexity

• Time: O(log n) evaluations of f
• Space: O(1)

Solution Code

Python

def find_peak_of_function(f, lo, hi):
    while lo < hi:
        mid = (lo + hi) // 2
        if f(mid) < f(mid + 1):
            lo = mid + 1
        else:
            hi = mid
    return lo  # index of the maximum

Java

// f is any unimodal function: int -> comparable value
int findPeakOfFunction(IntUnaryOperator f, int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (f.applyAsInt(mid) < f.applyAsInt(mid + 1)) lo = mid + 1;
        else hi = mid;
    }
    return lo;  // index of the maximum
}

C++

// f is any unimodal function: int -> comparable value
int findPeakOfFunction(function<int(int)> f, int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (f(mid) < f(mid + 1)) lo = mid + 1;
        else hi = mid;
    }
    return lo;  // index of the maximum
}

Key Takeaways

• Works whenever the function is unimodal — you never need it sorted.
• Binary search on the slope uses ~log n evaluations; ternary search uses ~2x more.
• Reference: unimodal optimisation; compare with ternary search and LeetCode 162.