Wie implementiert man eine binäre Suche in PHP? (Codebeispiel)

Binäre Suche (oder binäre Suche) ist eine Suchtechnik, die zum Suchen nach Elementen in einem sortierten Array verwendet wird. Wie implementiert man also die binäre Suche in PHP? Der folgende Artikel stellt Ihnen vor, wie Sie Iteration und Rekursion zur Implementierung der binären Suche in PHP verwenden. Ich hoffe, er wird Ihnen hilfreich sein. [Video-Tutorial-Empfehlung: PHP-Tutorial]

Methode 1: Iteration verwenden

Schritte:

1. Sortieren Sie das Array, da die binäre Suche nur für sortierte Bereiche funktioniert

2. Wenn das zu durchsuchende Element größer als das rechte If ist Das mittlere Element wird durchsucht, das mittlere Element wird berechnet, andernfalls wird die Suche auf der linken Seite berechnet.

3. Wenn das Element gefunden wird, wird True zurückgegeben.

Implementierungscode:

<?php 
header("content-type:text/html;charset=utf-8");
function binarySearch(Array $arr, $x) 
{ 
    // check for empty array 
    if (count($arr) === 0) return false; 
    $low = 0; 
    $high = count($arr) - 1; 
      
    while ($low <= $high) { 
          
        // 计算中间索引
        $mid = floor(($low + $high) / 2); 
   
        // 在中间找到元素
        if($arr[$mid] == $x) { 
            return true; 
        } 
  
        if ($x < $arr[$mid]) { 
            // 搜索数组的左侧
            $high = $mid -1; 
        } 
        else { 
            // 搜索数组的右侧
            $low = $mid + 1; 
        } 
    } 
      
    // 元素x不存在,返回false
    return false; 
} 
  
$arr = array(1, 2, 3, 4, 5); 
$value = 5; 
if(binarySearch($arr, $value) == true) { 
    echo "元素".$value."： 存在"; 
} 
else { 
    echo "元素".$value."： 不存在"; 
} 
?>

Ausgabe:

元素5： 存在

Methode 2: Rekursion verwenden

Rekursion ist die Art und Weise, wie wir dieselbe Funktion wiederholt aufrufen, bis eine Grundbedingung erfüllt ist, um die Rekursion zu beenden. Das Prinzip ist das gleiche wie bei Methode eins. Ändern Sie einfach die Parameter der Funktion rekursiv und zerlegen Sie das Problem.

Implementierungscode:

<?php 
header("content-type:text/html;charset=utf-8");
function binarySearch(Array $arr, $start, $end, $x){ 
    if ($end < $start) 
        return false; 
   
    $mid = floor(($end + $start)/2); 
    if ($arr[$mid] == $x)  
        return true; 
  
    elseif ($arr[$mid] > $x) { 
  
        // 调用binarySearch()函数本身， 改变其中参数：$start, $mid-1
        return binarySearch($arr, $start, $mid - 1, $x); 
    } 
    else { 
  
        // 调用binarySearch()函数本身， 改变其中参数：mid + 1, end
        return binarySearch($arr, $mid + 1, $end, $x); 
    } 
} 
  
$arr = array(1, 2, 3, 4, 5); 
$value = 6; 
if(binarySearch($arr, 0, count($arr) - 1, $value) == true) { 
    echo "元素".$value."： 存在"; 
} 
else { 
    echo "元素".$value."： 不存在"; 
} 
?>

Ausgabe:

元素6： 不存在

Das Obige ist der gesamte Inhalt dieses Artikels, ich hoffe, er wird für das Lernen aller hilfreich sein . Weitere spannende Inhalte finden Sie in den entsprechenden Tutorial-Kolumnen auf der chinesischen PHP-Website! ! !

Das obige ist der detaillierte Inhalt vonWie implementiert man eine binäre Suche in PHP? (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!