宽屏模式

二分查找算法

  • Larwas
  • 2019-06-21 06:25:10
  • php
  • PHP

二分查找

  • 也称折半查找（Binary Search）
  • 要求线性表采用顺序存储结构
  • 要求其中元素按关键字有序排列

一般步骤

  1. 确定要查找的区间
  2. 确定二分参照点
  3. 选取二分点
  4. 根据二分点的值，舍去一半无用区间
  5. 在有效区间重复上述步骤

算法源码

/**
 * 二分查找算法
 * @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;
}

本文为Larwas原创文章,转载无需和我联系,但请注明来自larwas博客 https://larwas.com

Larwas
请先登录后发表评论
  • latest comments
  • 总共0条评论