4

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

Yeti
  • 2,647
  • 2
  • 33
  • 37
  • Is Usage of array data structure important? – Alex Aparin Nov 19 '16 at 19:06
  • Not really, it can also be an unknown function `f(x)`, for a given `x` a value is measured. This is similar to having an input array of discrete values for `x` and an output array in which the result is available. Why do you ask? – Yeti Nov 20 '16 at 16:57
  • My idea was usage of binary search tree. Such that root is always maximum. It can o optimize search of maximum. – Alex Aparin Nov 20 '16 at 17:40

3 Answers3

1

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.

FDavidov
  • 3,505
  • 6
  • 23
  • 59
  • Your algorithm does not address duplicates. If you land in the middle of a sequence of 46 identical elements, what do you set `mid` to in order to complete in just 10 iterations? And by the way my algorithm *does* apply when the max is at either end. Perhaps you misunderstood how. – גלעד ברקן Nov 19 '16 at 19:06
1

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

Kaidul
  • 15,409
  • 15
  • 81
  • 150
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.

  • 1
    I used this approach. Actually, I gave it a parameter `k`. That is, for `k = 2` it is binary search, for `k = 3` it is ternary search, and for higher values of `k` it simply looks at values further toward the `begin` and `end` boundaries. Additionally, for approximate measurements, it can also be implemented to check if `abs(f(low) - f(high))` is smaller than some value, and if it is, then do both `low` and `high` as `begin` and `end` values. But this was not really necessary in my case after all. – Yeti Nov 24 '16 at 07:58