PHP implementiert einen binären Suchalgorithmus (detaillierte Codeerklärung)

Die binäre Suche wird auch als halbe Suche bezeichnet. Der binäre Suchalgorithmus erfordert, dass die Daten in Ordnung sind. Das Folgende ist der Code zum Implementieren des binären Suchalgorithmus in PHP.

1: Rekursive Methode

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
$target = 73;
$low = 0;
$high = count($array)-1;
function bin_search($array, $low, $high, $target){
    if ( $low <= $high){
        var_dump($low, $high);echo "\n";
        $mid =  intval(($low+$high)/2 );
        if ($array[$mid] ==  $target){
            return true;
        }elseif ( $target < $array[$mid]){
            return  bin_search($array, $low,  $mid-1, $target);
        }else{
            return  bin_search($array, $mid+ 1, $high, $target);
        }
    }
    return false;
}
$find = bin_search($array, $low, $high, $target);
var_dump($find);

Ausführungsergebnisse

int(0)
int(25)
int(13)
int(25)
int(20)
int(25)
int(20)
int(21)
bool(true)

Wir sehen, dass nach 4 binären Suchen das Suchintervall kontinuierlich halbiert und schließlich gefunden wird $target.

Zwei: Schleifenmethode

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
$target = 73;
function bin_search($array, $target)
{
    $low = 0;
    $high = count($array)-1;
    $find = false;
    while (true){
        if ($low <= $high){
            var_dump($low, $high);echo "\n";
            $mid = intval(($low + $high)/2);
            if ($array[$mid] == $target){
                $find = true;
                break;
            } elseif ($array[$mid] < $target){
                $low = $mid+1;
            } elseif ($array[$mid] > $target){
                $high = $mid-1;
            }
        } else {
            break;
        }
    }
    return $find;
}
$find = bin_search($array, $target);
var_dump($find);

Ausführungsergebnis

int(0)
int(25)
int(13)
int(25)
int(20)
int(25)
int(20)
int(21)
bool(true)

Wir sehen, dass der Prozess und die Ergebnisse der beiden Methoden gleich sind. Testen wir den binären Suchalgorithmus für assoziative Arrays:

$array = ['a'=>1,'b'=>3,'c'=>6,'d'=>9,'e'=>13,'f'=>18,'g'=>19,'h'=>29,'i'=>38];
$target = 19;
function bin_search($array, $target)
{
    $low = 0;
    $high = count($array)-1;
    $key_map = array_keys($array);
    $find = false;
    while (true){
        if ($low <= $high){
            var_dump($low, $high);echo "\n";
            $mid = intval(($low + $high)/2);
            if ($array[$key_map[$mid]] == $target){
                $find = true;
                break;
            } elseif ($array[$key_map[$mid]] < $target){
                $low = $mid+1;
            } elseif ($array[$key_map[$mid]] > $target){
                $high = $mid-1;
            }
        } else {
            break;
        }
    }
    return $find;
}
$find = bin_search($array, $target);
var_dump($find);
执行结果
int(0)
int(8)
int(5)
int(8)
bool(true)

Bei zwei binären Suchvorgängen wurde $target gefunden. Für assoziative Arrays haben wir die Funktion array_keys von PHP verwendet, um den Schlüssel dieses assoziativ geordneten Arrays zu ermitteln target und $array indirekt über den Schlüssel.

Das obige ist der detaillierte Inhalt vonPHP implementiert einen binären Suchalgorithmus (detaillierte Codeerklärung). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!