Wyszukiwanie maksimum lokalnego cz I. - wyszukiwanie ternarne

Mamy daną tablicę A[1..n] wypełnioną parami różnymi liczbami rzeczywistymi. Element, który jest większy od swoich sąsiadów nazywamy maksimum lokalnym. W tej notce przedstawię algorytm, który dla danej tablicy znajdzie (jakieś) maksimum lokalne.
W pierwszej kolejności sprawdźmy elementy A[1] oraz A[n]. Mają one tylko jednego sąsiada. Jeśli zatem A[1] jest większe niż A[2] albo A[n] jest większe od A[n-1] to znaleźliśmy maksimum lokalne i kończymy algorytm.
Co jednak jeśli tak nie jest? Wyobraźmy sobie tablice jako wierzchołki. Krawędź między dwoma wierzchołkami jest skierowana w stronę większego elementu. Mamy zatem taką sytuację:
Algorytm działa rekurencyjnie. Oznaczmy zatem element najbardziej na lewo jako A[l], a najbardziej na prawo jako A[r]. Niezmiennikiem naszego wywołania rekurencyjnego będzie to że element A[l] jest mniejszy od A[l+1] a element A[r] jest mniejszy od elementu A[r-1] (rysunek powyżej). Można łatwo udowodnić że w takim przedziale znajduje się maksimum lokalne.
Weźmy dwa środkowe elementy tablicy. Oznaczmy je jako A[p] oraz A[q]. Zapytajmy się który z nich jest większy.
Jeśli A[p] < A[q] to rozwiązanie znajduje się w przedziale A[p..r].
Jeśli A[p] > A[q] to rozwiązanie znajduje się w przedziale A[l..q].
Nie zdarzy się, ża A[p] = A[q] bo założyliśmy że elementy są parami różne. Algorytm zatrzymuje się gdy w dostajemy tablicę 3 elementową (można łatwo udowodnić, że na taką tablicę trafimy: gdy natrafiamy na tablicę rozmiaru 4 to następnie uruchamiamy się dla tablicy 3 elementowej; gdy natrafimy na tablicę rozmiaru 5 to następnie uruchamiamy się dla tablicy albo 3 elementowej albo 4 elementowej). Gdy natrafimy na tablicę 3 elementową to zgodnie z niezmiennikiem algorytmu jego środkowy element będzie maksimum lokalnym.
Algorytm jako że w każdej iteracji wykonuje stałą liczbę operacji, a zawsze przedział dzielony jest na "prawie" połowę to działa w czasie O(lg n).
Jeśli elementy w tablicy najpierw rosną, a potem maleją (lub odwrotnie) to tablica taka ma tylko jedno maksimum (minimum) lokalne i jest nim największy (najmniejszy) element w tablicy. Zatem w tego rodzajach tablic jesteśmy w stanie znaleźć element największy (najmniejszy) w czasie logarytmicznym!