Wskaż złożoność obliczeniową algorytmu wyszukiwania binarnego elementu w posortowanej tablicy n liczb.
A. O(log n)
B. O(n3)
C. O(n2)
D. O(n!)
Wyszukiwanie binarne ma złożoność O(log n), ponieważ w każdym kroku odrzuca mniej więcej połowę pozostałych elementów tablicy. Warunek jest jednak ważny: tablica musi być posortowana. Algorytm sprawdza element środkowy, a potem decyduje, czy szukana wartość jest po lewej, czy po prawej stronie. Dla 1 000 000 elementów nie trzeba sprawdzać miliona pozycji, tylko około 20 porównań, bo log₂(1 000 000) to mniej więcej 20. To jest ogromna różnica w praktyce, szczególnie przy dużych zbiorach danych, np. wyszukiwaniu identyfikatora użytkownika, numeru indeksu, rekordu w uporządkowanej tablicy albo zakresu cen. Moim zdaniem to jeden z najlepszych przykładów, który pokazuje po co analizuje się złożoność obliczeniową. W dobrej praktyce programistycznej zawsze trzeba też pamiętać o koszcie przygotowania danych: jeśli tablica nie jest posortowana, samo sortowanie może kosztować więcej niż jedno wyszukiwanie. Dlatego wyszukiwanie binarne najbardziej opłaca się wtedy, gdy po tym samym posortowanym zbiorze szukamy wiele razy.
Wyszukiwanie binarne nie działa tak, że przegląda wszystkie możliwe kombinacje albo wykonuje zagnieżdżone pętle po całej tablicy. Jego siła polega na tym, że po każdym porównaniu zawęża obszar poszukiwań o połowę. Dlatego złożoności takie jak O(n²), O(n³) czy O(n!) są zdecydowanie za duże i opisują zupełnie inne klasy problemów. O(n²) kojarzy się zwykle z algorytmami, gdzie mamy dwie pętle zależne od rozmiaru danych, np. proste porównywanie każdej pary elementów. O(n³) pojawia się przy jeszcze cięższych obliczeniach, często z trzema poziomami iteracji, na przykład w naiwnych metodach dla macierzy lub grafów. O(n!) to już złożoność silniowa, typowa dla sprawdzania wszystkich permutacji, jak w brutalnym podejściu do problemu komiwojażera. To kompletnie nie pasuje do wyszukiwania w uporządkowanej tablicy. Typowy błąd myślowy polega na tym, że ktoś widzi tablicę n elementów i automatycznie zakłada, że trzeba sprawdzić dużo, może nawet wszystko. Przy wyszukiwaniu liniowym byłoby O(n), ale binarne wykorzystuje porządek danych, więc zachowuje się znacznie lepiej. Z mojego doświadczenia warto zapamiętać prostą intuicję: jeśli algorytm w każdym kroku dzieli problem na pół, bardzo często w analizie pojawia się logarytm. Oczywiście trzeba pilnować indeksów lewy, prawy i środek, bo błędna implementacja może się zapętlić, ale poprawna idea nadal daje O(log n).