php演算法二分

『壹』 php二分查找問題

$inx=binarySearch($arr,13);

binarySearch返回數組下標值
然後再$arr[$inx]

『貳』 php二分查找遞歸和非遞歸的區別

binarySearch

二分查找採用的方法比較容易理解，以數組為例，

先取數組中間的值floor((low+top)/2),
然後通過與所需查找的數字進行比較，若比中間值大，則將首值替換為中間位置下一個位置，繼續第一步的操作；若比中間值小，則將尾值替換為中間位置上一個位置，繼續第一步操作
重復第二步操作直至找出目標數字
比如從1，3，9，23，54 中查找數字23，
首位置為0， 尾位置為4，中間位置就為2 值為9，比23小，則首位置更新為2+1即3；那麼接下來中間位置就為（3+4）/2=3，值為23，比較相等即找到
// 非遞歸
// $target是要查找的目標 $arr是已經排序好的數組
function binary(&$arr,$low,$top,$target){
while($low <= $top){
//由於php取商是有小數的，所以向下取整，不過也可不加，數組也會取整
$mid = floor(($low+$top)/2);
echo $mid."<br>";
if($arr[$mid]==$target){
return $arr[$mid];
}elseif($arr[$mid]<$target){
$low = $mid+1;
}else{
$top = $mid-1;
}
}
return -1;
}
// 遞歸
function binaryRecursive(&$arr,$low,$top,$target){
if($low<=$top){
$mid = floor(($low+$top)/2);
if($mid==$target){
return $arr[$mid];
}elseif($arr[$mid]<$target){
return binaryRecursive($arr,$mid+1,$top,$target);
}else{
return binaryRecursive($arr,$low,$top-1,$target);
}
}else{
return -1;
}
}

『叄』 php 二分查找法 百思不得其解

這書好像是有問題，$array[$mid]這里就有問題，用最大最小值取中間值，作為數組元素得key，邏輯上就說不過去
----------------------------------------------
<?php
//$k為要查找的關鍵字（註：待查找的數組元素為奇數個）
function bin_sch($array, $low, $high, $k)
{
if ($low <= $high)
{
$mid = intval(($low+$high)/2);
if ($array[$mid] == $k)
{
return true;
}
elseif ($k < $array[$mid])
{
return bin_sch($array, $low, $mid-1, $k);
}
else
{
return bin_sch($array, $mid+1, $high, $k);
}
}
return false;
}
$array = array(1, 2, 4, 6, 8, 20, 22);
$k = 20;
if(bin_sch($array, min(array_keys($array)), max(array_keys($array)), $k))
{
echo "二分查找成功";
}
else{
echo "二分查找失敗";
}
?>

改了一下

『肆』 PHP二分查找演算法的實現方法示例

本文實例講述了PHP二分查找演算法的實現方法。分享給大家供大家參考，具體如下：
二分查找法需要數組是一個有序的數組
假設我們的數組是一個遞增的數組，首先我們需要找到數組的中間位置.
1.
要知道中間位置就需要知道起始位置和結束位置，然後取出中間位置的值來和我們的值做對比。
2.
如果中間值大於我們的給定值，說明我們的值在中間位置之前，此時需要再次二分，因為在中間之前，所以我們需要變的值是結束位置的值，此時結束位置的值應該是我們此時的中間位置。
3.
反之，如果中間值小於我們給定的值，那麼說明給定值在中間位置之後，此時需要再次將後一部分的值進行二分，因為在中間值之後，所以我們需要改變的值是開始位置的值，此時開始位置的值應該是我們此時的中間位置，直到我們找到指定值。
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;
}
//遞歸實現
/*
*
從數組中獲取元素值
*
@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;
}
更多關於PHP相關內容感興趣的讀者可查看本站專題：《PHP數據結構與演算法教程》、《PHP基本語法入門教程》、《php面向對象程序設計入門教程》、《php字元串(string)用法總結》及《php查找技巧與方法總結》
希望本文所述對大家PHP程序設計有所幫助。