close

Bináris keresési (Binary Search) algoritmus PHP-ben: magyarázat, lépések és példa

A bináris keresési algoritmus hatékony módszer egy adott érték megtalálására egy rendezett tömbben. Ez a megközelítés kisebb részekre osztja a tömböt, és folyamatosan összehasonlítja a keresési tartomány középső pozíciójában lévő értéket a célértékkel. Ha az értékek egyeznek, a kívánt érték megtalálható; Ellenkező esetben az algoritmus tovább szűkíti a keresési tartományt, és addig ismétli a folyamatot, amíg meg nem találja az értéket, vagy nem marad több elemet vizsgálni.

Lépések:

  1. A keresési tartomány inicializálása: Kezdje a keresési tartomány kiválasztásával  a tömb első pozíciójától left  az utolsó pozícióig. right
  2. Középpont keresése: left A középpont kiszámítása a és a jobb pozíciók átlagolásával ; ez a keresési tartomány középső pontja.
  3. Értékek összehasonlítása: Hasonlítsa össze a középső pont értéket a célértékkel.
  4. Összehasonlítási eredmény kezelése: Ha a középső pont értéke megegyezik a célértékkel, adja vissza ezt a pozíciót. Ha a középső pont értéke kisebb, mint a célérték, frissítse a bal oldali pozíciót középre + 1 a jobb fele kereséséhez. Ha a középső pontban lévő érték nagyobb, mint a célérték, frissítse a jobb oldali pozíciót a középső- 1 értékre a bal fele kereséséhez.
  5. Ismétlés: Ismételje meg a 2–4. lépéseket mindaddig, amíg meg nem találja az értéket, vagy nincs több ellenőrizendő elem left > right.

Előnyök és hátrányok

Előnyök:

  • Hatékony teljesítmény: Az algoritmus időbeli összetettsége O(log n), így rendkívül hatékony nagy adathalmazok kezelésére.
  • Hatékony nagy adatkészletek esetén: A bináris keresés hatékonyan csökkenti a gyorsan megvizsgálandó elemek számát nagy adatkészletek esetén.

Hátrányok:

  • Csak rendezett tömbökre vonatkozik: Az algoritmus csak rendezett tömbökön működik.
  • Változó lépések száma: Az érték megtalálásához szükséges lépések száma a tömbben elfoglalt helyétől függ, és sok lépést is igénybe vehet a végekhez közeli értékek esetén.

Példa: Bináris keresés a 12-es érték megtalálásához egy rendezett tömbben PHP-ben 

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

A példa magyarázata

  1. A kezdeti keresési tartományból indulunk ki a  tömb első pozíciójától left = 0 az utolsó pozícióig. right = 6
  2. A középpontot(középpontot) a bal és jobb pozíciók átlagolásával számítjuk ki; mid = 3. A középső érték 12.
  3. Összehasonlítjuk a mid(12) értéket a célértékkel(12), és találunk egyezést, így a 3. pozíciót adjuk vissza.
  4. Az algoritmus véget ér, és a következő eredményt adjuk ki: "12. érték található a 3. pozícióban."