Fast algorithm for finding maximum in a bell-shaped list of values

Question

I have a list of values that is increasing to a maximum and then decreasing again (it is an observed gaussian/bell-shaped distribution).

values = [0, 4, 5, 15, 30, 20, 10, 5, 0];

But the distribution can also be shifted:

values = [0, 0, 0, 1, 2, 3, 8, 15, 30];

Or similarly:

values = [30, 20, 5, 2, 1, 1, 0, 0, 0];

Determining a value at a specific index is very costly in this specific application, so it is important to use the least possible amount of array lookups.

Solutions such as hill climbing or a variant of binary search should work. What is the algorithm with the least possible steps?

The long lookup-time is due to a real-world measuring device (time in order of seconds).

Answer 1

You are looking for ternary search, possibly with some heuristics from interpolation search.

Basically, start with

def search(f, begin, end):
    if end - begin <= 3:
        return max(map(f, range(begin, end)))
    low = (begin * 2 + end) / 3
    high = (begin + end * 2) / 3
    if f(low) > f(high):
        return search(f, begin, high - 1)
    else:
        return search(f, low + 1, end)

Asymptotically, it is the best you can do without relying on some properties of your values. If it is not "good enough", change expressions for low and high to better match your real data.