close

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

Den binære søgealgoritme er en effektiv metode til at finde en bestemt værdi i et sorteret array. Denne tilgang opdeler arrayet i mindre dele og sammenligner løbende værdien i den midterste position af søgeområdet med målværdien. Hvis værdierne stemmer overens, findes den ønskede værdi; ellers fortsætter algoritmen med at indsnævre søgeområdet og gentager processen, indtil værdien er fundet, eller der ikke er flere elementer tilbage at undersøge.

Trin:

  1. Initialiser søgeområdet: Begynd med at vælge søgeområdet fra den første position left  til den sidste position right  i arrayet.
  2. Find midtpunktet: Beregn midtpunktet ved at tage et gennemsnit af left og højre positioner; dette er midtpunktet i søgeområdet.
  3. Sammenlign værdier: Sammenlign værdien i midtpunktet med målværdien.
  4. Håndter sammenligningsresultat: Hvis værdien i midterpunktet matcher målværdien, returner denne position. Hvis værdien ved det midterste punkt er mindre end målværdien, skal du opdatere venstre position til midterste + 1 for at søge i højre halvdel. Hvis værdien ved det midterste punkt er større end målværdien, skal du opdatere den højre position til midten- 1 for at søge i venstre halvdel.
  5. Gentag: Gentag trin 2 til 4, indtil værdien er fundet, eller der ikke er flere elementer at kontrollere left > right.

Fordele og ulemper

Fordele:

  • Effektiv ydeevne: Algoritmens tidskompleksitet er O(log n), hvilket gør den yderst effektiv til håndtering af store datasæt.
  • Effektiv til store datasæt: Binær søgning er effektiv til at reducere antallet af elementer, der skal undersøges hurtigt for store datasæt.

Ulemper:

  • Gælder kun for sorterede arrays: Algoritmen virker kun på sorterede arrays.
  • Variabelt antal trin: Antallet af trin, der kræves for at finde værdien, afhænger af dens position i arrayet, og det kan tage mange trin for værdier nær enderne.

Eksempel: Binær søgning for at finde værdien 12 i et sorteret array 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 af eksemplet

  1. Vi starter med det indledende søgeområde fra den første position left = 0 til den sidste position right = 6  i arrayet.
  2. Vi beregner midtpunktet(midt) ved at tage et gennemsnit af venstre og højre position; mid = 3. Værdien ved midten er 12.
  3. Vi sammenligner værdien ved mid(12) med målværdien(12) og finder et match, så vi returnerer position 3.
  4. Algoritmen slutter, og vi udsender resultatet "Værdi 12 fundet ved position 3."