PHP 二分法查找数据
作者：会飞的
不论在PHP中还是在其他的编程语言中，使用顺序法查找数据都面临着一个很大的问题，那就是：如果数组中的数据很多时，该怎么办？
继续使用顺序法查找数据会使得PHP的效率变低。
这时我们引入了二分法查找数据。
二分法就是在PHP的数组中假象数组排好序了，然后通过对数组元素的比较得到结果。比较一次就会排出1/2的数组。
例如：
<?php
//函数名称为Dichotomy，$php为数组，$k为要查找的值，$low为最小的值，$max为最大值
function Dichotomy($php,$k,$low,$max)
{
if(count($php)!= 0 and $max == 0)
{
$max = count($php);
}
if($low <= $max)
{
$mid = intval(($low+$max)/2);
if($php[$mid] == $k)
{
return $mid;
}
else if($k < $php[$mid])
{
return Dichotomy($php,$k,$low,$mid-1);
}
else
{
return Dichotomy($php,$k,$mid+1,$max);
}
}
return -1;
}
$php = array('1','2','3','4','5','6');
echo Dichotomy($php,5);
?>
结果：
Warning: Missing argument 3 for Dichotomy(), called in E:xampphtdocsphpTest8.5.2.php on line 29 and defined in E:xampphtdocsphpTest8.5.2.php on line 3
Warning: Missing argument 4 for Dichotomy(), called in E:xampphtdocsphpTest8.5.2.php on line 29 and defined in E:xampphtdocsphpTest8.5.2.php on line 3
4
这是我第一次做的时候呈现的错误。问题出在哪里呢？
好吧：新手问题。因为在函数刚开始没有给$low和$max赋值，使得函数的if没有办法进行。
正确的代码如下：
<?php
//函数名称为Dichotomy，$php为数组，$k为要查找的值，$low为最小的值，$max为最大值
function Dichotomy($php,$k,$low=0,$max=0)
{
if(count($php)!= 0 and $max == 0)
{
$max = count($php);
}
if($low <= $max)
{
$mid = intval(($low+$max)/2);
if($php[$mid] == $k)
{
return $mid;
}
else if($k < $php[$mid])
{
return Dichotomy($php,$k,$low,$mid-1);
}
else
{
return Dichotomy($php,$k,$mid+1,$max);
}
}
return -1;
}
$php = array('1','2','3','4','5','6');
echo Dichotomy($php,5);
?>
结果是：
4
返回的是键值。
这个PHP例子说的是在已知数组排序的情况和所需要查找的数据下所进行的：将数组中的最小和最大值相加取平均，因为已经知道所要查找的元素了，就比如我这个例子，所以从$mid+1到$max开始查找。
这样我们会想：天下哪里有这么便宜的事，谁实现知道所有的数组呢。所以，这种方法也不是很方便。
那么，你有什么建议呢？