Jak znaleźć igłę w cyfrowym stogu siana? Wyszukiwanie liniowe vs binarne

Wyobraź sobie, że stoisz przed regałem w bibliotece miejskiej, na którym stoi 100 000 książek, a Ty szukasz podręcznika do przygotowania pod egzamin INF.04.

Możesz podejść do pierwszego woluminu z lewej, przeczytać grzbiet, przejść do drugiego, trzeciego... i tak do wieczora. Albo możesz wykorzystać fakt, że ktoś ułożył te książki alfabetycznie, podejść dokładnie na środek regału i rozwiązać problem w 17 sekund.

Dzisiaj rozbierzemy na czynniki pierwsze dwa fundamentalne algorytmy: Linear Search oraz Binary Search.

Przykład z życia: Książka telefoniczna

Zanim bazy danych i smartfony zjadły świat, ludzie korzystali z papierowych książek telefonicznych (takich grubych tomów mających 1000 stron z nazwiskami od A do Z).

Szukasz nazwiska Nowak:

1. Podejście Linear Search: Otwierasz stronę 1: Adamski. Strona 2: Adamiak. Strona 3: Augustyniak... Będziesz wertować kartka po kartce przez pół dnia. Jeśli szukasz kogoś na literę „Ż”, masz gwarantowany ból nadgarstka.
2. Podejście Binary Search: Otwierasz książkę dokładnie w połowie. Trafiasz na literę M. Wiesz, że litera N jest w alfabecie dalej niż M. Co robisz? Ignorujesz całą pierwszą połowę książki. Zostaje Ci 500 stron. Otwierasz je w połowie - trafiasz na R. „N” jest wcześniej! Wyrzucasz strony od R do Z. Zostało Ci 250 stron. Powtarzasz ten manewr jeszcze kilka razy i w ułamku minuty masz przed oczami nazwisko Nowaka.

To właśnie potęga strategii Dziel i zwyciężaj (Divide and Conquer).

Starcie wagi ciężkiej: Złożoność obliczeniowa

W programowaniu nie oceniamy algorytmów po tym, jak szybko działają na 5 elementach, ale jak zachowują się, gdy dane rosną do milionów (notacja Big O).

• Wyszukiwanie liniowe (Linear Search) - Złożoność $ O(n) $:
  eśli tablica ma $ n $ elementów, w najgorszym scenariuszu sprawdzisz wszystkie $ n $ pozycji.
  1 000 elementów = 1 000 operacji.
  1 000 000 000 elementów = 1 000 000 000 operacji. Czas rośnie proporcjonalnie do rozmiaru danych.
• Wyszukiwanie binarne (Binary Search) - Złożoność $ O(log  n) $:
  Logarytm o podstawie 2 to pojęcie matematyczne, które dla programisty oznacza jedno: za każdym podejściem dzielimy problem na dwa.

Spójrzmy na liczby, bo one robią piorunujące wrażenie:

💡 Zapamiętaj: Podwojenie wielkości tablicy przy wyszukiwaniu binarnym zwiększa liczbę operacji o... zaledwie 1 krok.

Kod w akcji: Binary Search w Javie

Oto elegancka, iteracyjna implementacja algorytmu w języku Java. Zwróć uwagę na wskaźniki left, right oraz sposób obliczania środka (mid):

public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            // Bezpieczny sposób na obliczenie środka (chroni przed integer overflow)
            int mid = left + (right - left) / 2;
            // Trafiliśmy w dziesiątkę!
            if (array[mid] == target) {
                return mid;
            }
            // Jeśli szukany element jest mniejszy, odcinamy prawą połówkę
            if (target < array[mid]) {
                right = mid - 1;
            } 
            // W przeciwnym razie szukamy wyłącznie w prawej połówce
            else {
                left = mid + 1;
            }
        }
        // Element nie istnieje w tablicy
        return -1;
    }

Wielka Pułapka Architektoniczna: Kiedy NIE używać Binary Search?

Wyszukiwanie binarne brzmi jak cheat-code w grze RPG, ale ma dwa krytyczne ograniczenia, o które regularnie pytają na egzaminach zawodowych i rozmowach kwalifikacyjnych (Junior Devs często na tym wpadają):

1. Warunek posortowania:
   Jeśli dostajesz tablicę z losowymi danymi i musisz sprawdzić obecność elementu tylko jeden raz, użycie QuickSort $ O(n  log  n) $ + Binary Search $ O(log  n) $ będzie wielokrotnie wolniejsze niż zwykły Linear Search $ O(n) $. Nie opłaca się sprzątać całego pokoju tylko po to, żeby znaleźć w nim jedną skarpetkę. Sortowanie opłaca się wtedy, gdy po jednorazowym uporządkowaniu bazy będziesz pytać o dane tysiące razy!
2. Dostęp swobodny (Random Access):
   Binary Search działa błyskawicznie na klasycznych tablicach (Array, ArrayList), bo skok do array[mid] odbywa się w czasie stałym $ O(1) $. Gdybyś spróbował odpalić ten algorytm na liście wiązanej (LinkedList), musiałbyś przejść po wskaźnikach węzeł po węźle, żeby dotrzeć na środek, co całkowicie rujnuje sens tej optymalizacji.