二分查找及快速排序

小朋友

二分查找和快速排序思想上有很大的相似度，就是做一个起始点，开始往左右做动作，也同样是由递归实现，当然也可以不用递归实现。

但是我觉得也不能用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 循环。

我选择用递归，递归的方式更直白和简单，更符合以上所说逻辑，好理解。

binarySearch 函数 $array为数组，$k为要找的值，$low 为查找范围的最小键值，$high 为查找范围的最大键值

public function binarySearch($array, $k, $low = 0, $high = 0){
//判断数组元素的数量
    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 "没有要查找的值";
    }

原文链接:二分查找及快速排序-PHP