CODEWITHSUNDEEP
arraysmax
xgmexgme
xgmexgme

Reputation: 139

finding 2 peaks in an array

I have an array which has an order like

increasing, decreasing, increasing, decreasing.

I want to find out what are two local maximum elements at the end of increasing behaviors. I know i can find them O(n) time, i wonder whether it is possible to find it in O(log n) time or better than O(n) time.

Upvotes: 1

Views: 763

Answers (1)

Jake Staines
Jake Staines

Reputation: 98

If you don't know that your data follows that specific pattern - increase then decrease then increase then decrease - then the best you can do is O(n), because you're going to have to examine every single item in the array to determine which the two highest points are.

If you know that it definitely does follow that pattern, then my best guess is an adaptation of binary search, which goes roughly:

  • pick the middle point of the data set, check the 'gradient' - the difference between two successive values.
  • use this to divide the data set in half, check the middle points of your two new spaces again; you want to keep subdividing in this manner until you find you have enough data points that you have a down, then an up, in that order. Between these two points is one of the troughs, and to the left of the first down, and to the right of the last up, are the peaks you're looking for.
  • perform a binary search of those two spaces to find the actual peaks - again, check two values each time to find the gradient rather than just sampling single values, so you can tell which direction to keep searching in.

Without doing the maths, my off-the-top-of-my-head guess is that this algorithm is O(2log(n)) at best, O(n) at worst. It'll certainly be pretty rare that it takes you as long as searching the entire data set, and I think you'd need a trivially small data set to take longer than the naive search.

Upvotes: 2

Related Questions