close

Algoritam binarnog pretraživanja (Binary Search) u PHP-u: objašnjenje, koraci i primjer

Algoritam binarnog pretraživanja učinkovita je metoda za pronalaženje određene vrijednosti u sortiranom nizu. Ovaj pristup dijeli niz na manje dijelove i kontinuirano uspoređuje vrijednost na srednjoj poziciji raspona pretraživanja s ciljnom vrijednošću. Ako se vrijednosti podudaraju, željena vrijednost je pronađena; u suprotnom, algoritam nastavlja sužavati raspon pretraživanja i ponavlja proces dok se ne pronađe vrijednost ili dok više ne ostane nijedan element za ispitivanje.

koraci:

  1. Inicijalizirajte raspon pretraživanja: Započnite odabirom raspona pretraživanja od prve left  do zadnje pozicije right  u nizu.
  2. Pronađite srednju točku: Izračunajte srednju točku izračunavanjem prosjeka left položaja i desno; ovo je središnja točka raspona pretraživanja.
  3. Usporedite vrijednosti: Usporedite vrijednost na srednjoj točki s ciljnom vrijednošću.
  4. Rezultat usporedbe ručke: Ako vrijednost na srednjoj točki odgovara ciljanoj vrijednosti, vratite ovu poziciju. Ako je vrijednost na srednjoj točki manja od ciljane vrijednosti, ažurirajte lijevu poziciju na sredinu + 1 za pretraživanje desne polovice. Ako je vrijednost u srednjoj točki veća od ciljane vrijednosti, ažurirajte desnu poziciju na sredinu- 1 za pretraživanje lijeve polovice.
  5. Ponavljanje: Ponavljajte korake od 2 do 4 dok se ne pronađe vrijednost ili dok nema više elemenata za provjeru left > right.

Prednosti i nedostatci

Prednosti:

  • Učinkovita izvedba: vremenska složenost algoritma je O(log n), što ga čini vrlo učinkovitim za rukovanje velikim skupovima podataka.
  • Učinkovito za velike skupove podataka: binarno pretraživanje učinkovito smanjuje broj elemenata za brzo ispitivanje za velike skupove podataka.

Nedostaci:

  • Primjenjivo samo na sortirane nizove: Algoritam radi samo na sortiranim nizovima.
  • Varijabilni broj koraka: Broj koraka potrebnih za pronalaženje vrijednosti ovisi o njenom položaju u nizu, a može biti potrebno mnogo koraka za vrijednosti blizu krajeva.

Primjer: Binarno pretraživanje za pronalaženje vrijednosti 12 u sortiranom nizu u PHP-u 

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.";  
}

Objašnjenje primjera

  1. Počinjemo s početnim rasponom pretraživanja od prve left = 0 do zadnje pozicije right = 6  niza.
  2. Srednju točku(sredinu) izračunavamo usrednjavanjem lijevog i desnog položaja; mid = 3. Vrijednost na sredini je 12.
  3. Uspoređujemo vrijednost na mid(12) s ciljnom vrijednošću(12) i nalazimo podudaranje, pa vraćamo poziciju 3.
  4. Algoritam završava i ispisujemo rezultat "Vrijednost 12 pronađena na poziciji 3."