php算法 - 二分查找 2019-09-23

二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

查找过程：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法要求：


1.必须采用顺序存储结构。

2.必须按关键字大小有序排列。




其实，说白了 ，就是当我们有一个这样的数组[1,5,9,10,11,16,23,25,31,35,48,52,56,59,60,67];

我们要找出某个值的位置时，例如16在哪个位置时，应该如何快速找到他？如果从头往后找，或者从尾往前找，是不是很慢？如果数组N长，我们的查找就有可能是N次。

而二分查找就不一样了。

直接折半。比如上面例子数组有16个元素。 16/2=8那就是从 arr[8] 这个位置开始找。首先我们判断16是否等于 arr[8]这个值 如果等于返回，不等于则判断是否大于/小于 ，如果大于，则往上找，小于则往下找。

按照上面例子。

像上面例子，找到为16的过程仅仅只有 3次就能找到。如果我们仅仅使用循环，则要循环到第6次才能真正找到他的位置。




OK，我们贴代码（我上的是递归版，循环版的大家可以自行模仿写一个，也可以百度查找demo）




/**
 * 
 * @param array $container 数组
 * @param type $search要找的数据
 * @param type $low 开始位置
 * @param type $top结束位置
 * @return string 返回 如果找到则是位置的key，如果没找到则是返回没找着哦
 */
function BinaryQueryRecursive(array $container, $search, $low = 0, $top = 'default') {

    $top == 'default' && $top = count($container);
    if ($low <= $top) {
        $mid = intval(floor($low + $top) / 2);
        if (!isset($container[$mid])) {
            return '没找着哦';
        }
        if ($container[$mid] == $search) {
            return $mid;
        }
        if ($container[$mid] < $search) {
            return BinaryQueryRecursive($container, $search, $mid + 1, $top);
        } else {
            return BinaryQueryRecursive($container, $search, $low, $mid - 1);
        }
    }
}

$container = [1, 5, 9, 10, 11, 16, 23, 25, 31, 35, 48, 52, 56, 59, 60, 67];
echo BinaryQueryRecursive($container, 16);







给大家个图自己看看逻辑是这样的，例子显示搜39，第一次是蓝色这条的搜索，第二次是橙色，第三次绿色。三次完成。