php - @amazeUI - 2016-11-28 11:45:31
二分查找和快速排序思想上有很大的相似度，就是做一个起始点，开始往左右做动作，也同样是由递归实现，当然也可以不用递归实现。但是我觉得也不能用php内置特有的函数- -，我找了很多php的快速排序，几乎都用到了array_merge函数。当然使用的array_merge函数里的那个快速排序也是快排思想- -。
public function quickSort($left,$right,&$arr)
{
$l= $left;
$r= $right;
$pivot= $arr[($left + $right)/ 2];
$temp= 0;
while ($l< $r) {
while ($arr[$l]< $pivot) {
$l++;
}
while ($arr[$r]> $pivot) {
$r--;
}
if ($l>= $r) {
break;
}
$temp= $arr[$l];
$arr[$l]= $arr[$r];
$arr[$r]= $temp;
if ($arr[$l]== $pivot) {
--$r;
}
if ($arr[$r]== $pivot) {
++$l;
}
}
if ($l== $r) {
$l++;
$r--;
}
if ($left < $r) {
self::quickSort($left, $r,$arr);
}
if ($right > $l) {
self::quickSort($l,$right,$arr);
}
}
下面是二分查找:
摸索二分查找法，对于php数组而言，要找一个值太容易了，array_search一下就好了。二分查找又叫做折半查找。假设我在纸上写了一个整数，在零到一百之间，需要你来猜我纸上写的到底是几，这个怎么猜？最快速的办法就是做二分查找，假设纸上的数字为10，已知范围为0到100，先将范围值折半，猜50，再询问50是比纸上的数字大还是小，答案是小了，再将范围值缩小至0-50，再次折半，猜25。。。这样才是最快的方式。用代码实现二分查找法，基本有两个方式，一个是递归，一个是while循环。我选择用递归，递归的方式更直白和简单，更符合以上所说逻辑，好理解。
//$search 函数 $array为数组，$K为要找的值，$low为查找范围的最小键值，$high为查找范围的最大键值
public function binarySearch($array, $k, $low = 0, $high = 0)
{
//判断数组元素的数量
echo 1;
if (count($array) != 0 and $high == 0) { //判断是否为第一次调用
//数组的元素个数
$high = count($array);
}
if ($low <= $high) { //如果还存在剩余的数组元素
$mid = intval(($low + $high) / 2); //取$low 与$high的中间值3
//return $array[$mid];
if ($array[$mid] == $k) {
return $mid; //如果找到则返回
} elseif ($array[$mid] > $k) {//如果要找的值小于中间值
//如果上面没有找到，则继续查找
return self::binarySearch($array, $k, $low, $mid - 1);
} else {
return self::binarySearch($array, $k, $mid + 1, $high);//5-11,8-11,9-11,10-11,10+11/2再取整还是10，开始死循环---
}
}
return "没有要查找的值";
}
