PHP如何實作二進位搜尋？ （程式碼範例）

二進位搜尋（折半查找）是一種用來搜尋排序數組中元素的搜尋技術。那麼PHP中如何實現二進位搜尋呢？以下這篇文章就來跟大家介紹在PHP中如何使用迭代和遞歸方式來實現二進制搜索，希望對大家有所幫助。 【影片教學推薦：PHP教學】

方法一：使用迭代

#步驟：

1、對陣列進行排序，因為二進位搜尋只適用於已排序的範圍

2、如果我們要搜尋的元素大於右側的中間元素搜索，則計算中間元素，否則計算左側的搜索。

3、如果找到元素，則傳回True。

實作程式碼：

<?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."： 不存在"; 
} 
?>

#輸出：

元素5： 存在

方法二：使用遞迴

##遞歸是我們重複呼叫相同函數直到符合基本條件以結束遞歸的方式。原理和方法一相同，只需以遞歸的方式更改函數的參數並分解問題。

實作程式碼：

<?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."： 不存在"; 
} 
?>

#輸出：

元素6： 不存在

以上就是這篇文章的全部內容，希望能對大家的學習有所幫助。更多精彩內容大家可以追蹤php中文網相關教學欄位！ ！ ！

以上是PHP如何實作二進位搜尋？ （程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！