Beispielcode für die binäre PHP-Suche für rekursive und nicht rekursive Implementierungen

Binäre Suche, auch als halbe Suche bekannt, hat den Vorteil weniger Vergleiche, eine schnelle Suchgeschwindigkeit und eine gute durchschnittliche Leistung. Der Nachteil besteht darin, dass die nachzuschlagende Tabelle geordnet sein muss Tabelle und EinfügenLöschenSchwierig. Daher eignet sich die binäre Suchmethode für geordnete Listen, die sich nicht häufig ändern, aber häufig durchsucht werden. Unter der Annahme, dass die Elemente in der Tabelle in aufsteigender Reihenfolge angeordnet sind, vergleichen Sie zunächst das in der mittleren Position der Tabelle aufgezeichnete Schlüsselwort mit dem Suchschlüsselwort. Wenn die beiden gleich sind, ist die Suche erfolgreich. Andernfalls wird der Datensatz in der mittleren Position verwendet Teilen Sie die Tabelle in zwei Untertabellen, die erste und die letzte. Wenn das in der mittleren Position aufgezeichnete Schlüsselwort größer als das Suchschlüsselwort ist, wird die vorherige Untertabelle weiter durchsucht, andernfalls wird die nächste Untertabelle durchsucht weiter. Wiederholen Sie den obigen Vorgang, bis ein Datensatz gefunden wird, der die Bedingungen erfüllt, wodurch die Suche erfolgreich ist, oder bis die Untertabelle nicht mehr vorhanden ist. In diesem Fall schlägt die Suche fehl.

Die Grundidee der binären Suche besteht darin, n Elemente in zwei ungefähr gleiche Teile zu teilen, a[n/2] mit x zu vergleichen, wenn x=a[n/2], x zu finden und den Algorithmus abzubrechen ; wenn xSuche nach x in der linken Hälfte von Arraya fort, wenn Sie die rechte Hälfte von Array a nach x durchsuchen.

Das Folgende ist der Beispielcode

// 递归二分查找
$arr = [1,2,3,4,11,12,124,1245];
function bin_recur_find($arr, $beg, $end, $v) {
	if ($beg <= $end) {
		$idx = floor(($beg + $end)/2);
		if ($v == $arr[$idx]) {
			return $idx;
		} else {
			if ($v < $arr[$idx]) {
				return bin_recur_find($arr, $beg, $idx - 1, $v);
			} else {
				return bin_recur_find($arr, $idx + 1, $end, $v);
			}
		}
	}
	return -1;
}
// 非递归二分查找
function bin_find($arr, $v) {
	$beg = 0;
	$end = count($arr) - 1;
	while ($beg <= $end) {
		$idx = floor(($beg + $end)/2);
		if ($v == $arr[$idx]) {
			return $idx;
		} else {
			if ($v < $arr[$idx]) {
				$end = $idx - 1;
			} else {
				$beg = $idx + 1;
			}
		}
	}
	return -1;
}

echo bin_recur_find($arr, 0, count($arr) - 1, 100) . "\n";
echo bin_find($arr, 100) . "\n";

Das obige ist der detaillierte Inhalt vonBeispielcode für die binäre PHP-Suche für rekursive und nicht rekursive Implementierungen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!