PHPで実装された二分探索アルゴリズムの分析例-PHPチュートリアル-php.cn

PHPで実装された二分探索アルゴリズムの分析例

小云云

リリース： 2023-03-18 06:14:01

オリジナル

1502 人が閲覧しました

この記事では、PHP で実装される二分探索アルゴリズムの原理と、ループや再帰などの実装テクニックをサンプル形式で紹介します。。

二分探索法では、配列が順序付けられた配列である必要があります

配列が増加する配列であると仮定すると、まず配列の中間位置を見つける必要があります。

1 つ。中間位置を知るには、開始位置と終了位置を知ってから、中間位置の値を取得してこの値と比較する必要があります。
2つ。中央の値が指定した値より大きい場合は、この時点で値が中央より前にあることを意味します。中央より前なので、変更する必要がある値はです。このとき、終了位置の値は「We're in the middle at this point」となるはずです。
3つ。一方、中間の値が与えた値より小さい場合は、与えられた値が中間の位置より後であることを意味します。このとき、後半の値はであるため、再度 2 つに分割する必要があります。中間値の後なので、変更する必要がある値は開始位置の値です。指定された値が見つかるまで、この時点の開始位置の値が中間位置になります。
4つ。または、中間値が最初の開始位置または終了位置と等しい場合 (この場合、指定された値が見つかりません)、コードを使用して実装しましょう~

//循环实现
function getValue($num,$arr)
{
//查找数组的中间位置
$length=count($arr);
$start=0;
$end=$length;
$middle=floor(($start+$end)/2);
//循环判断
while($start>$end-1)
{
if($arr[middle]==$num)
{
return middle+1;
}elseif($arr[middle]<$num)
{
//如果当前要查找的值比当前数组的中间值还要打，那么意味着该值在数组的后半段
//所以起始位置变成当前的middle的值，end位置不变。
$start=$middle;
$middle=floor(($start+$end)/2);
}else{
//反之
$end=$middle;
$middle=floor(($start+$end)/2);
}}
return false;
}

ログイン後にコピー

//循环实现
function getValue($num,$arr)
{
//查找数组的中间位置
$length=count($arr);
$start=0;
$end=$length;
$middle=floor(($start+$end)/2);
//循环判断
while($start>$end-1)
{
if($arr[middle]==$num)
{
return middle+1;
}elseif($arr[middle]<$num)
{
//如果当前要查找的值比当前数组的中间值还要打，那么意味着该值在数组的后半段
//所以起始位置变成当前的middle的值，end位置不变。
$start=$middle;
$middle=floor(($start+$end)/2);
}else{
//反之
$end=$middle;
$middle=floor(($start+$end)/2);
}}
return false;
}

ログイン後にコピー