close

Binær søkealgoritme (Binary Search) i PHP: Forklaring, trinn og eksempel

Algoritmen for binær søk er en effektiv metode for å finne en spesifikk verdi i en sortert matrise. Denne tilnærmingen deler opp arrayet i mindre deler og sammenligner kontinuerlig verdien i midtposisjonen av søkeområdet med målverdien. Hvis verdiene stemmer overens, blir ønsket verdi funnet; Ellers fortsetter algoritmen å begrense søkeområdet og gjentar prosessen til verdien er funnet eller det ikke er flere elementer igjen å undersøke.

Trinn:

  1. Initialiser søkeområdet: Begynn med å velge søkeområdet fra den første posisjonen left  til den siste posisjonen right  i arrayen.
  2. Finn midtpunktet: Beregn midtpunktet ved å beregne gjennomsnittet av left og høyre posisjoner; dette er midtpunktet i søkeområdet.
  3. Sammenlign verdier: Sammenlign verdien på midtpunktet med målverdien.
  4. Håndter sammenligningsresultat: Hvis verdien på midtpunktet samsvarer med målverdien, returner denne posisjonen. Hvis verdien ved midtpunktet er mindre enn målverdien, oppdater venstre posisjon til midten + 1 for å søke i høyre halvdel. Hvis verdien ved midtpunktet er større enn målverdien, oppdater høyre posisjon til midten- 1 for å søke i venstre halvdel.
  5. Gjenta: Gjenta trinn 2 til 4 til verdien er funnet eller det ikke er flere elementer å sjekke left > right.

Fordeler og ulemper

Fordeler:

  • Effektiv ytelse: Tidskompleksiteten til algoritmen er O(log n), noe som gjør den svært effektiv for håndtering av store datasett.
  • Effektivt for store datasett: Binært søk er effektivt for å redusere antall elementer som skal undersøkes raskt for store datasett.

Ulemper:

  • Gjelder bare for sorterte matriser: Algoritmen fungerer kun på sorterte matriser.
  • Variabelt antall trinn: Antall trinn som kreves for å finne verdien avhenger av dens posisjon i matrisen, og det kan ta mange trinn for verdier nær enden.

Eksempel: Binært søk for å finne verdien 12 i en sortert matrise i 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.";  
}

Forklaring av eksempelet

  1. Vi starter med det innledende søkeområdet fra den første posisjonen left = 0 til den siste posisjonen right = 6  i matrisen.
  2. Vi beregner midtpunktet(midten) ved å beregne gjennomsnittet av venstre og høyre posisjon; mid = 3. Verdien ved midten er 12.
  3. Vi sammenligner verdien ved mid(12) med målverdien(12) og finner et samsvar, så vi returnerer posisjon 3.
  4. Algoritmen avsluttes, og vi sender ut resultatet "Verdi 12 funnet ved posisjon 3."