CODEWITHSUNDEEP
algorithmbinary-searchhill-climbing
Yeti
Yeti

Reputation: 2845

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

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).

Upvotes: 4

Views: 2728

Answers (3)

Kaidul
Kaidul

Reputation: 15875

As FDavidov mentioned, you should go with variant of binary search as you only need to access around ceil[O(logn)] indices in worst case.

The pseudo-code of binary search variant will look like this:

left := 0
right := n - 1
while left < right do
    mid := left + (right - left) / 2
    if values[mid] > values[mid + 1] 
         right := mid
    else
         left := mid 
end

print left

However, to find maximum or minimum point in non-convex shaped graph, ternary search works best. But ternary search cuts space based on some non-integer evaluation function which doesn't suit best for integers.

If you don't need exact result and close approximation is acceptable, you can try ternary search too.

enter image description here

Upvotes: 1

user2512323
user2512323

Reputation:

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.

Upvotes: 1

FDavidov
FDavidov

Reputation: 3675

Assuming that you don't have local maxima (as it would normally happen with measurements), binary lookup is the fastest way. If you have, say, 1000 data points, you would end up with about 10 checks in the worst case when the maximum is somewhere in the middle.

To cope with the situation at which the maximum is either to the right or left of your data (like in your second and third examples), you can simply start by checking if either of the two ends is higher to its contiguous point and, if it does, you end up your search with no more than two checks.

Upvotes: 1

Related Questions