二分查找的定义

原理

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

步骤

• 确定要查找的区间
• 确定要二分的参照点
• 区间内选取二分点
• 根据二分点的值，综合左右间情况以及求见的目的，舍去一般无用的区间
• 继续在有效区间重复上面的步骤

PHP实现

function binary_search($arr, $number)
{
    if (!is_empty($arr) || empty($arr)) {
        return -1;
    }
    // 初始变量值
    $len = count($arr);
    $lower = 0;
    $high = $len - 1;

    // 最低点比最高点大就退出
    while ($lower <= $high) {

        // 以中间点作为参照点比较
        $middle = intval(($lower + $high) / 2);
        if ($arr[$middle] > $number) {
            // 查找数比参照点小，舍去右边
            $high = $middle - 1;
        } elseif ($arr[$middle] < $number) {
            // 查找树比参照点大，舍去左边
            $lower = $middle + 1;
        } else {
            return $middle;
        }
    }

    return -1;
}

/**
* @param array $arr
* @param int $number
* @param int $lower
* @param int $hith
*/
function binary_search_recursion(&$arr, $number, $lower, $high)
{
    $middle = intval(($lower + $high) / 2);

    if ($lower > $high) {
        return -1;
    }

    if ($number > $arr[$middle]) {
        return __FUNCTION__($arr, $number, $middle, $high);
    } elseif ($number < $arr[$middle]) {
        return __FUNCTION__($arr, $number, $lower, $middle - 1);
    } else {
        return $middle;
    }
}

时间复杂度

• 有序数组中如果使用暴力的算法去查找，也就是逐个遍历比较，那么时间复杂度是O(n)
• 但是，用二分查找后，因为每次可以舍去一半查找区间，所以会将时间复杂度减少到O(logn)，算法更优。

本作品采用《CC 协议》，转载必须注明作者和本文链接