php二分検索
5702 ワード
PHP実現二分ルックアップ
二分ルックアップに必要な配列は秩序化された配列であり,我々の配列が増加した配列であると仮定すると,まず配列の中間位置を見つける必要がある.
一、中間位置を知るには、開始位置と終了位置を知ってから、中間位置の値を取り出して私たちの値と比較する必要があります.
二、もし中間値が私たちの所与の値より大きいならば、私たちの値が中間位置の前にあることを説明して、この時再び二分する必要があります.中間の前にあるので、私たちが変化する値は終了位置の値で、この時の終了位置の値は私たちのこの時の中間位置であるべきです.
三、逆に、もし中間値が私たちが与えた値より小さいならば、与えられた値が中間位置の後にあることを説明して、この時再び後の部分の値を二分する必要があります.中間値の後で、私たちが変更しなければならない値は開始位置の値で、この時の開始位置の値は私たちが指定した値を見つけるまで、私たちのこの時の中間位置であるべきです.
四、または中間値が最初の開始位置に等しいか、終了位置(指定された値が見つからないことを示す)
コードで実装します
1、循環実現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
2、再帰実現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
以上の内容は参考までに!
二分ルックアップに必要な配列は秩序化された配列であり,我々の配列が増加した配列であると仮定すると,まず配列の中間位置を見つける必要がある.
一、中間位置を知るには、開始位置と終了位置を知ってから、中間位置の値を取り出して私たちの値と比較する必要があります.
二、もし中間値が私たちの所与の値より大きいならば、私たちの値が中間位置の前にあることを説明して、この時再び二分する必要があります.中間の前にあるので、私たちが変化する値は終了位置の値で、この時の終了位置の値は私たちのこの時の中間位置であるべきです.
三、逆に、もし中間値が私たちが与えた値より小さいならば、与えられた値が中間位置の後にあることを説明して、この時再び後の部分の値を二分する必要があります.中間値の後で、私たちが変更しなければならない値は開始位置の値で、この時の開始位置の値は私たちが指定した値を見つけるまで、私たちのこの時の中間位置であるべきです.
四、または中間値が最初の開始位置に等しいか、終了位置(指定された値が見つからないことを示す)
コードで実装します
1、循環実現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
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;
}
2、再帰実現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
/*
*
* @param1 int $num,
* @param2 array $arr,
* @param3 int $start,
* @param4 int $end,
* @return mixed, , false
*/
function
getValue4(
$num
,
$arr
,
$start
= 0,
$end
= 100){
//
$middle
=
floor
((
$end
+
$start
) / 2);
//
if
(
$arr
[
$middle
] ==
$num
){
// ,
return
$middle
+ 1;
}
elseif
(
$arr
[
$middle
] <
$num
){
//
$start
=
$middle
+ 1;
//
if
(
$start
>=
$end
){
// , ,
return
false;
}
// :
return
getValue4(
$num
,
$arr
,
$start
,
$end
);
//getValue4($num,$arr,51,100)
}
else
{
//
$end
=
$middle
- 1;
//
if
(
$end
< 0)
return
false;
// :
return
getValue4(
$num
,
$arr
,
$start
,
$end
);
//getValue4($num,$arr,0,49)
}
//
return
false;
}
以上の内容は参考までに!