二分查找算法

1,060 阅读2分钟

俗话说,面试造飞机,工作拧螺丝。拧了3年螺丝,也该造造飞机了。

打算面试头条,据说算法要求很高,先从基本的热热身。

二分查找算法

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

算法复杂度:log2(n)

查找逻辑:

  1. 假设线性表升序排列。
  2. 将表中间位置数据和查找的数据进行比较,如果相等,则查找成功,返回索引值。
  3. 否则,将当前线性表切分为前表和后表。
  4. 如果当前值小于目标值,则从后表继续查找。
  5. 如果大于目标值,则从前表继续查找。
  6. 重复以上过程,直到查找成功,或者子表不存在。

Javascript实现方式

/**
 * 二分查找算法
 * @params value 需要查找的目标值
 * @params arr 需要查找目标值的数组,即单向线性表
 * @params start 开始查找的下标
 * @params end 结束查找的下标
 * @return 查找到目标值,返回对应下标;否则,返回-1
 */
function divide2Find(value, arr, start, end) {
    // 如果等于左右两侧,直接返回;否则当查找范围<2,则表明该值不存在
    if (value === arr[start]) {
        return start;
    } else if (value === arr[end]) {
        return end;
    } else if (end - start < 2) {
        return -1;
    }
    // 二分,取中间值比较;如果不匹配,根据大小指定方向,二分递归查找
    let index = Math.floor((start + end) / 2);
    let cur = arr[index];
    if (cur === value) {
        return index;
    } else if (cur > value) {
        return divide2Find(value, arr, start, index);
    } else {
        return divide2Find(value, arr, index, end)
    }
}

// 算法函数调用
const arr = [3, 5, 6, 7, 9, 12, 15];
divide2Find(5, [3, 5, 6, 7, 9, 12, 15], 0, arr.length - 1);  // 1
divide2Find(13, [3, 5, 6, 7, 9, 12, 15], 0, arr.length - 1);  // -1

PHP实现方式

除了语法之外,和上面的JS思路完全一致,不再赘述注释。

function divide2Find($value, $arr, $start, $end) {
    if ($value === $arr[$start]) {
        return $start;
    } else if ($value === $arr[$end]) {
        return $end;
    } else if ($end - $start < 2) {
        return -1;
    }
    $index = floor(($end + $start) / 2);
    $cur = $arr[$index];
    if ($cur === $value) {
        return $index;
    } else if ($cur > $value) {
        return $this->divide2Find($value, $arr, $start, $index);
    } else {
        return $this->divide2Find($value, $arr, $index, $end);
    }
}

// 算法函数调用
$arr = [3, 5, 6, 7, 9, 12, 15];
echo $this->divide2Find(5, $arr, 0, count($arr) - 1);  // 1
echo $this->divide2Find(13, $arr, 0, count($arr) - 1);  // -1