Programista ma za zadanie zaimplementować funkcję, która będzie często wyszukiwać elementy w dużej, posortowanej kolekcji danych. Który algorytm wyszukiwania zapewni najlepszą średnią wydajność (najniższą złożoność czasową)?

Poprawna odpowiedź: B

Uzasadnienie i szersze wyjaśnienie:

Kluczową informacją w pytaniu jest to, że kolekcja danych jest posortowana. Ta cecha umożliwia zastosowanie znacznie wydajniejszych algorytmów niż proste przeszukiwanie liniowe.

• Wyszukiwanie binarne to algorytm, który działa na zasadzie „dziel i zwyciężaj”. W każdym kroku porównuje szukany element z elementem środkowym w kolekcji. Jeśli szukany element jest mniejszy, odrzuca prawą połowę kolekcji; jeśli jest większy, odrzuca lewą. Dzięki temu w każdym kroku liczba elementów do przeszukania zmniejsza się o połowę. Złożoność czasowa tego algorytmu to O(log n), co jest niezwykle wydajne dla dużych zbiorów danych.

Dlaczego pozostałe odpowiedzi są nieprawidłowe?

• A. Wyszukiwanie liniowe (sekwencyjne): Sprawdza każdy element po kolei. Jego złożoność to O(n). Dla dużej kolekcji jest to bardzo wolne i nie wykorzystuje faktu, że dane są posortowane.
• C. Wyszukiwanie z wartownikiem: Jest to jedynie niewielka optymalizacja wyszukiwania liniowego. Jego złożoność wciąż wynosi O(n).
• D. Wyszukiwanie interpolacyjne: Jest to wariant wyszukiwania binarnego, który może być jeszcze szybszy (średnia złożoność O(log log n)) pod warunkiem, że dane są równomiernie rozłożone. Jednak wyszukiwanie binarne ma lepszą gwarantowaną wydajność w najgorszym przypadku (O(log n) vs O(n) dla interpolacyjnego) i jest standardowym, najlepszym wyborem dla ogólnych, posortowanych danych.