PHP を使用して二分探索アルゴリズムのコード共有を実装する

最初の方法:
[二分探索の要件]: 1. 順次記憶構造を使用する必要があります。 2. キーワードのサイズに応じて順番に配置する必要があります。
【長所と短所】半減検索法の利点は、比較が少なく、検索速度が速く、平均パフォーマンスが良いことです。欠点は、検索するテーブルが順序付けされたテーブルである必要があり、挿入と削除が難しいことです。 。したがって、二分探索法は、頻繁には変更されないが、頻繁に検索される順序付きリストに適しています。
[アルゴリズムの考え方] まず、表の中央に記録されたキーワードと検索キーワードを比較し、一致しない場合は、中央のレコードを使用して表を先頭と最後に分割します。中間位置のレコードが検索キーワードより大きい場合は、前のサブテーブルがさらに検索され、それ以外の場合は、次のサブテーブルがさらに検索されます。

<?php 
//正向排序的数组 
$arr=array(1,3,5,7,9,11); 
//逆向排序的数组 
$arr2=array(11,9,7,5,3,1); 
//对正向排序的数组进行二分查找 
function searchpart($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);//这里只需要保证中间项下标的计算值为整数即可，也可以四舍五入，不影响结果 
if($arr[$mid]>$x){//如果中间项的值大于待查值，说明代差值位于中间项的左边，因此，起始下标不变，结束下标变成中间项下标减1，第一次搜索的是$arr[0]-$arr[5]的话，下一次搜索 
$end=$mid-1;//$arr[0]-$arr[1] 
}elseif($arr[$mid]<$x){//如果中间项的值小于待查值，说明代差值位于中间项的右边，因此，结束下标不变，起始下标变成中间项下标加1，第一次搜索的是$arr[0]-$arr[5]的话，下一//次搜索是，$arr[3]-$arr[5] 
$start=$mid+1; 
}else{//找到了，返回待查值下标 
return $mid; 
} 
} 
} 
//对逆向排序的数组进行二分查找 
function searchpart2($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);//这里只需要保证中间项下标的计算值为整数即可，也可以四舍五入，不影响结果 
if($arr[$mid]>$x){//如果中间项的值大于待查值，说明代差值位于中间项的右边，因此，结束下标不变，起始下标变成中间项下标加1，第一次搜索的是$arr[0]-$arr[5]的话，下一次搜索 
$start=$mid+1;//$arr[3]-$arr[5] 
}elseif($arr[$mid]<$x){//如果中间项的值小于待查值，说明代差值位于中间项的左边，因此，起始下标不变，结束下标变成中间项下标减1，第一次搜索的是$arr[0]-$arr[5]的话，下一//次搜索是，$arr[0]-$arr[1] 
$end=$mid-1; 
}else{//找到了，返回待查值下标 
return $mid; 
} 
} 
} 
echo searchpart2($arr,5).&#39;<br>&#39;; 
echo searchpart2($arr2,5); 
?>

PHPでの二分探索アルゴリズムの実装
以前学んだアルゴリズムの知識を最近整理しました WEB開発ではあまり使わないアルゴリズムですが、それでも役立つアルゴリズムをいくつかバックアップしておきます。
半探索法は二分探索法とも呼ばれ、要素間の順序関係を利用し、最悪の場合はO(log n)で探索タスクを完了することができます。 。
【基本的な考え方】
n個の要素をほぼ同じ数で2等分し、a[n/2]と求めたいxを比較し、x=a[n/2]であればxを求め、アルゴリズムは終了します。 。 xa[n/2] の場合、配列 a の右半分で x の検索を続けるだけで済みます。
二分探索法は非常に広く使われており、その考え方は理解しやすいです。最初の二分探索アルゴリズムは 1946 年には登場しましたが、最初の完全に正しい二分探索アルゴリズムは 1962 年まで登場しませんでした。 Bentley は著書「Writing Correct Programs」の中で、コンピュータ専門家の 90% は 2 時間以内に完全に正しい二分探索アルゴリズムを書くことができないと書いています。この問題の鍵は、各検索範囲の境界を正確に定式化し、終了条件を決定し、奇数と偶数のさまざまな状況を正確に要約することです。実際、それを整理すると、その特定のアルゴリズムが非常に複雑であることがわかります。直感的。
PHP での二分探索アルゴリズムの実装

/** 
* 二分查找算法 
* 
* @param array $arr 有序数组 
* @param int $val 查找的数值 
* @return int 查找值存在返回数组下标,不存在返回-1 
*/ 
function binary_search($arr,$val) 
{ 
$l = count($arr);//获得有序数组长度 
$low = 0; 
$high = $l -1; 
while($low <= $high) 
{ 
$middle = floor(($low + $high) / 2); 
if($arr[$middle] == $val) 
{ 
return $middle; 
} 
elseif($arr[$middle] > $val) 
{ 
$high = $middle - 1; 
} 
else 
{ 
$low = $middle + 1; 
} 
} 
return -1; 
} 
//示例 
$arr = array(1,2,3,4,5,6,7,8,9,12,23,33,35,56,67,89,99); 
echo binary_search($arr,57);

PHP を使用して二分探索アルゴリズムを実装するコード共有の詳細については、PHP 中国語 Web サイトに注目してください。