Wyszukiwanie binarne – O(log n) vs O(n) z tabelą porównawczą

Wyszukiwanie liniowe działa zawsze. Przelatujesz przez każdy element po kolei i w końcu znajdziesz to, czego szukasz. Problem pojawia się przy 100 000 elementach, gdy robisz to w pętli. Wyszukiwanie binarne rozwiązuje ten problem elegancko – ale tylko jeśli dane są posortowane. Pokazuję implementację w PHP i sytuacje, gdzie naprawdę robi różnicę.

Wyszukiwanie liniowe – punkt odniesienia

<?php

function linearSearch(array $arr, mixed $target): int
{
    foreach ($arr as $index => $value) {
        if ($value === $target) {
            return $index;
        }
    }

    return -1; // nie znaleziono
}

$data = range(1, 100000);
echo linearSearch($data, 99999); // w najgorszym przypadku - 99999 porównań

Złożoność: O(n). Przy n = 100 000 elementów w najgorszym przypadku wykonujesz 100 000 porównań.

Wyszukiwanie binarne – implementacja iteracyjna

Warunek wstępny: tablica musi być posortowana. Algorytm za każdym razem dzieli przestrzeń przeszukiwania na pół:

<?php

function binarySearch(array $arr, mixed $target): int
{
    $left  = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = intdiv($left + $right, 2);

        if ($arr[$mid] === $target) {
            return $mid; // znaleziono, zwróć indeks
        }

        if ($arr[$mid] < $target) {
            $left = $mid + 1; // szukaj w prawej połowie
        } else {
            $right = $mid - 1; // szukaj w lewej połowie
        }
    }

    return -1; // nie znaleziono
}

$data = range(1, 100000);
echo binarySearch($data, 99999); // maksymalnie 17 porównań (log2 z 100000 ≈ 17)

Złożoność: O(log n). Przy n = 100 000 elementów potrzebujesz maksymalnie 17 porównań. Przy n = 1 000 000 - tylko 20.

Wersja rekurencyjna

<?php

function binarySearchRecursive(array $arr, mixed $target, int $left, int $right): int
{
    if ($left > $right) {
        return -1;
    }

    $mid = intdiv($left + $right, 2);

    if ($arr[$mid] === $target) {
        return $mid;
    }

    if ($arr[$mid] < $target) {
        return binarySearchRecursive($arr, $target, $mid + 1, $right);
    }

    return binarySearchRecursive($arr, $target, $left, $mid - 1);
}

$data = range(1, 100000);
echo binarySearchRecursive($data, 42, 0, count($data) - 1); // 41

Wersja iteracyjna jest w PHP szybsza w praktyce – brak narzutu na wywołania rekurencyjne i ryzyka przekroczenia limitu zagnieżdżenia.

Wyszukiwanie binarne na tablicach asocjacyjnych

W praktyce rzadko szukasz po indeksie numerycznym. Częściej masz tablicę obiektów lub asocjacyjną posortowaną po jakimś kluczu:

<?php

function binarySearchByKey(array $arr, mixed $target, string $key): int
{
    $left  = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = intdiv($left + $right, 2);

        if ($arr[$mid][$key] === $target) {
            return $mid;
        }

        if ($arr[$mid][$key] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return -1;
}

// Posortowane produkty po cenie
$products = [
    ['name' => 'Gadget',     'price' => 9.99],
    ['name' => 'Doohickey',  'price' => 14.99],
    ['name' => 'Widget',     'price' => 29.99],
    ['name' => 'Thingamajig','price' => 49.99],
    ['name' => 'Contraption','price' => 99.99],
];

$index = binarySearchByKey($products, 29.99, 'price');
echo $products[$index]['name']; // Widget

Gdzie to ma realne zastosowanie?

W codziennej pracy z Magento i PHP rzadko implementujesz binary search od zera – ale zrozumienie algorytmu pomaga w konkretnych sytuacjach:

• Indeksy w bazie danych działają na podobnej zasadzie (B-tree). Rozumiesz dlaczego zapytanie bez indeksu na tabeli z milionem rekordów jest wolne
• in_array() na dużych tablicach to O(n). Jeśli szukasz w posortowanym zbiorze wielokrotnie – binary search lub przepisanie na tablicę asocjacyjną z isset() to O(1)
• Magento używa podobnych mechanizmów przy przeszukiwaniu katalogów produktów przez Elasticsearch – który sam w sobie jest oparty na indeksach odwróconych i strukturach drzewiastych

Porównanie złożoności

Podsumowanie

Wyszukiwanie binarne to klasyczny przykład na to, że wybór algorytmu ma znaczenie niezależnie od języka programowania. W PHP koszt pojedynczego porównania jest niski – ale przy dużych zbiorach danych różnica między O(n) a O(log n) jest gigantyczna. Warto mieć ten algorytm w głowie, nawet jeśli na co dzień korzystasz z gotowych narzędzi.