二分查找

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

算法的要求

必须采用顺序存储结构。
必须按关键字大小有序排列。

算法的步骤

其实，二分查找也还是比较容易理解的，大概就是一分为二，然后两边比较，保留有效区间，继续一分为二查找，直到找到或者超出区间则结束，所以二分查找的基本步骤是：

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

实现

/**
 * 二分查找算法
 * @param array $arr 待查找区间
 * @param int $number 查找数
 * @return int        返回找到的键
 */
function binary_search($arr, $number) {
    // 非数组或者数组为空，直接返回-1
    if (!is_array($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;
        } else if ($arr[$middle] < $number) {
            // 查找数比参照点大，舍去左边
            $lower = $middle + 1;
        } else {
            // 查找数与参照点相等，则找到返回
            return $middle;
        }
    }
    // 未找到，返回-1
    return -1;
}

 

递归算法

/**
 * @param array $arr 待查找区间
 * @param int $number 查找数
 * @param int $lower 区间最低点
 * @param int $high 区间最高点
 * @return int
 */
function binary_search_recursion(&$arr, $number, $lower, $high) {
    // 以区间的中间点作为参照点比较
    $middle = intval(($lower + $high) / 2);
    // 最低点比最高点大就退出
    if ($lower > $high) {
        return -1;
    }
    if ($number > $arr[$middle]) {
        // 查找数比参照点大，舍去左边继续查找
        return binary_search_recursion($arr, $number, $middle + 1, $high);
    } elseif ($number < $arr[$middle]) {
        // 查找数比参照点小，舍去右边继续查找
        return binary_search_recursion($arr, $number, $lower, $middle - 1);
    } else {
        return $middle;
    }
}