close

Binární vyhledávací (Binary Search) algoritmus v PHP: Vysvětlení, kroky a příklad

Algoritmus Binary Search je efektivní metoda k nalezení konkrétní hodnoty v seřazeném poli. Tento přístup rozdělí pole na menší části a průběžně porovnává hodnotu na střední pozici vyhledávacího rozsahu s cílovou hodnotou. Pokud se hodnoty shodují, je nalezena požadovaná hodnota; jinak algoritmus pokračuje ve zužování rozsahu hledání a opakuje proces, dokud není nalezena hodnota nebo nezbývají žádné další prvky ke zkoumání.

kroky:

  1. Inicializujte rozsah vyhledávání: Začněte výběrem rozsahu vyhledávání od první pozice left  po poslední pozici right  pole.
  2. Najděte prostřední bod: Vypočítejte prostřední bod zprůměrováním left pozic a pravých; toto je střední bod rozsahu vyhledávání.
  3. Porovnat hodnoty: Porovnejte hodnotu ve středu s cílovou hodnotou.
  4. Zpracovat výsledek porovnání: Pokud se hodnota ve středním bodě shoduje s cílovou hodnotou, vraťte tuto pozici. Pokud je hodnota ve středním bodě nižší než cílová hodnota, aktualizujte levou pozici na střední + 1, abyste prohledali pravou polovinu. Pokud je hodnota ve středním bodě větší než cílová hodnota, aktualizujte pravou pozici na střední- 1, abyste prohledali levou polovinu.
  5. Opakujte: Opakujte kroky 2 až 4, dokud nebude nalezena hodnota nebo nebudou žádné další prvky ke kontrole left > right.

Výhody a nevýhody

výhody:

  • Efektivní výkon: Časová složitost algoritmu je O(log n), díky čemuž je vysoce efektivní pro zpracování velkých souborů dat.
  • Efektivní pro velké datové sady: Binární vyhledávání je efektivní při snižování počtu prvků, které je třeba rychle prozkoumat u velkých datových sad.

Nevýhody:

  • Platí pouze pro setříděná pole: Algoritmus funguje pouze na setříděných polích.
  • Proměnný počet kroků: Počet kroků potřebných k nalezení hodnoty závisí na její pozici v poli a pro hodnoty blízko konců může provést mnoho kroků.

Příklad: Binary Search pro nalezení hodnoty 12 v seřazeném poli v PHP 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

Vysvětlení příkladu

  1. Začneme počátečním rozsahem hledání od první pozice left = 0 do poslední pozice right = 6  pole.
  2. Střední bod(mid) vypočítáme zprůměrováním levé a pravé polohy; mid = 3. Hodnota uprostřed je 12.
  3. Porovnáme hodnotu v mid(12) s cílovou hodnotou(12) a najdeme shodu, vrátíme tedy pozici 3.
  4. Algoritmus skončí a my vypíšeme výsledek "Hodnota 12 nalezená na pozici 3."