PHPで二分探索を実装するにはどうすればよいですか? (コード例)

二分検索 (半値検索) は、ソートされた配列内の要素を検索するために使用される検索手法です。では、PHP で二分検索を実装するにはどうすればよいでしょうか?次の記事では、反復と再帰を使用して PHP で二分探索を実装する方法を紹介します。 [ビデオチュートリアルの推奨: PHP チュートリアル ]

方法 1: 反復を使用する ##手順:

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： 存在

方法 2: 再帰を使用する

再帰とは、基本条件が一致して再帰が終了するまで、同じ関数を繰り返し呼び出す方法です。原理は方法 1 と同じで、関数のパラメータを再帰的に変更して問題を分解するだけです。

実装コード:

<?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 中国語 Web サイトの関連チュートリアルのコラムに注目してください。 ！ ！

以上がPHPで二分探索を実装するにはどうすればよいですか? (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。