close

Binäärihakualgoritmi (Binary Search) PHP:ssä: Selitys, vaiheet ja esimerkki

Binäärihakualgoritmi on tehokas tapa löytää tietty arvo lajitetusta taulukosta. Tämä lähestymistapa jakaa taulukon pienempiin osiin ja vertaa jatkuvasti hakualueen keskikohdan arvoa kohdearvoon. Jos arvot täsmäävät, haluttu arvo löytyy; muussa tapauksessa algoritmi jatkaa hakualueen kaventamista ja toistaa prosessia, kunnes arvo löytyy tai tutkittavia elementtejä ei ole enää jäljellä.

Askeleet:

  1. Alusta hakualue: Aloita valitsemalla hakualue  taulukon ensimmäisestä paikasta left  viimeiseen kohtaan. right
  2. Etsi keskipiste: Laske keskipiste laskemalla keskiarvo oikeasta left ja oikeasta sijainnista; tämä on hakualueen keskipiste.
  3. Vertaa arvoja: Vertaa keskipisteen arvoa tavoitearvoon.
  4. Käsittele vertailutulos: Jos keskipisteen arvo vastaa tavoitearvoa, palauta tämä sijainti. Jos keskipisteen arvo on pienempi kuin tavoitearvo, päivitä vasen sijainti keskikohtaan + 1 etsiäksesi oikeaa puoliskoa. Jos arvo keskipisteessä on suurempi kuin tavoitearvo, päivitä oikea sijainti keskikohtaan- 1 etsiäksesi vasenta puoliskoa.
  5. Toista: Toista vaiheita 2–4, kunnes arvo löytyy tai tarkistettavia elementtejä ei ole enää left > right.

Hyödyt ja haitat

Edut:

  • Tehokas suorituskyky: Algoritmin aikamonimutkaisuus on O(log n), mikä tekee siitä erittäin tehokkaan suurten tietojoukkojen käsittelyssä.
  • Tehokas suurille tietojoukoille: Binaarihaku vähentää tehokkaasti suurten tietojoukkojen nopeasti tutkittavien elementtien määrää.

Haitat:

  • Koskee vain lajiteltuja taulukoita: Algoritmi toimii vain lajitetuissa taulukoissa.
  • Vaihtuva askelmäärä: Arvon löytämiseen tarvittavien vaiheiden määrä riippuu sen sijainnista taulukossa, ja se voi kestää useita vaiheita lähellä päitä oleville arvoille.

Esimerkki: Binaarihaku arvon 12 löytämiseksi järjestetyssä taulukossa PHP:ssä 

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

Esimerkin selitys

  1. Aloitamme alkuperäisestä hakualueesta  taulukon ensimmäisestä paikasta left = 0 viimeiseen kohtaan. right = 6
  2. Laskemme keskipisteen(keskipisteen) laskemalla keskiarvon vasemmasta ja oikeasta paikasta; mid = 3. Arvo puolivälissä on 12.
  3. Vertaamme arvoa kohdassa mid(12) tavoitearvoon(12) ja löydämme vastaavuuden, joten palautetaan sijainti 3.
  4. Algoritmi päättyy ja tulostamme tuloksen "Arvo 12 löydetty sijainnista 3."