Biorąc pod uwagę tablicę liczb całkowitych, znajdź lokalne minima. Element A [i] jest zdefiniowany jako lokalne minimum, jeśli A [i-1]> A [i] i A [i] <A [i + 1] gdzie i = 1 ... n-2. W przypadku elementów granicznych liczba musi być tylko mniejsza niż sąsiednia liczba.

Wiem, że jeśli istnieje tylko jedno lokalne minimum, możemy rozwiązać zmodyfikowane wyszukiwanie binarne. Ale jeśli wiadomo, że w tablicy istnieje wiele lokalnych minimów, czy można to rozwiązaćO(log n) czas?