Algorytm binarnych poszukiwań wykonuje zadanie wyszukiwania w ciągu uporządkowanym najlepiej z przedstawionych do tej pory algorytmów. Zastanówmy się, czy jest możliwe dalsze poprawienie kosztu.

Rozważmy klasę wszystkich algorytmów, które rozwiązują problem wyszukiwania w ciągu uporządkowanym przez porównywanie elementów. Dla ustalenia uwagi, niech każdy algorytm w rozważanej klasie, będzie całkowicie poprawny ze względu na specyfikację:

wp = {n > 1, e[1]< e[2]< ... < e[n], e[1] £ x < e[n]},        wk = { result £ n, e[result] £ x £ e[result+1]}.

Drzewem decyzyjnym dla danego algorytmu wyszukiwania nazywać będziemy drzewo binarne, którego wierzchołki wewnętrzne są etykietowane parami porównywanych elementów, liście zawierają wartości zmiennej result. Każdy wierzchołek wewnętrzny ma dwa następniki odpowiadające akcjom, które trzeba wykonać, gdy  porównanie w tym wierzchołku dało odpowiedź tak i  gdy dało odpowiedź nie. Każda ścieżka odpowiada  więc ciągowi porównań wykonanych przez algorytm dla konkretnych danych. Wartość znajdująca się w liściu (na tej ścieżce) jest uzyskanym wynikiem algorytmu. Oznaczmy przez D(Alg,n) drzewo decyzyjne dla algorytmu Alg i danych o rozmiarze n.

Przykład 5.1

Niech rozważanym algorytmem będzie algorytm poszukiwań sekwencyjnych Search. Wtedy drzewo decyzyjne dla dowolnego ciągu e[1], e[2], e[3], e[4],  zostało przedstawione na rysunku 2_1.

Niech rozważanym algorytmem będzie algorytm Skoki. Drzewo decyzyjne dla danych e[1], e[2],...,e[16] zostało przedstawione na rysunku 2_2.

Pytanie 5: Ile maksymalnie pytań TAK/NIE trzeba zadać, aby odgadnąć dowolną liczbę z przedziału [0,10⁶]?

NA mocy założenia wszystkie algorytmy rozważanej klasy zawsze dają poprawne wyniki, zatem wszystkie możliwe wyniki muszą się znaleźć jako etykiety liści w każdym z drzew decyzyjnych odpowiadających konkretnemu algorytmowi. Dla danych rozmiaru n, zmienna result, zgodnie ze specyfikacją przyjmować może tylko n-1 różnych wartości. Zatem liczba liści dowolnego drzewa decyzyjnego D(Alg,n) musi być co najmniej równa n-1. Oczywiście, liczba liści może być dużo większa niż n-1. Algorytm może wykonywać niepotrzebne porównania i wielokrotnie dochodzić do tego samego wyniku.

Liczba wykonanych porównań w konkretnym obliczeniu jest równa długości ścieżki od korzenia do liścia, zatem policzmy jak długie muszą być ścieżki. Zanotujmy najpierw prosty fakt dotyczący drzew binarnych.

Dowód lematu 5.1 można przeprowadzić przez proste rozumowanie indukcyjne ze względu na h.

Wróćmy do problemu długości ścieżek w drzewie decyzyjnym. Gdyby w jakimś drzewie decyzyjnym D(Alg,n) wszystkie ścieżki miały długość mniejszą niż lg(n-1), to wysokość tego drzewa byłaby mniejsza niż lg(n-1). Wtedy, na mocy lematu 5.1, liczba liści w tym drzewie byłaby mniejsza niż 2 ^lg(n-1), czyli mniejsza od (n-1). Zmienna result w algorytmie Alg nie przyjmowałaby jednej z możliwych wartości. To jednak jest niemożliwe, bo założyliśmy, że wszystkie algorytmy rozważanej klasy zawsze dają poprawne wyniki. Wynika stąd, że w każdym drzewie decyzyjnym musi istnieć jakaś ścieżka o długości co najmniej lg(n-1). Oznacza to, że w przypadku najgorszym liczba wykonanych porównań musi być co najmniej równa lg(n-1). Ponieważ musi to być liczba całkowita, zatem liczba wykonanych porównań w przypadku pesymistycznym wynosi co najmniej élg(n-1)ù.

Uzyskany wynik mówi, że dla dowolnego algorytmu rozwiązującego problem wyszukiwania przez porównywanie elementów, zawsze znajdą się takie dane, dla których algorytm wykona co najmniej Q(lg n) porównań.

Ponieważ algorytm BinSearch wykonuje w najgorszym przypadku élg nù porównań, zatem:

Pytanie 6: Który z algorytmów wyszukiwania w ciągu uporządkowanym został zastosowany, jeżeli wykonano kolejno porównania z elementami  ciągu o następujących indeksach  64, 95, 111, 103, 99, 97, 96? Ile elementów miał ten ciąg? .