Skip to content

1. 先确认查询条件 ​

查找是在数据中确认目标是否存在、位于哪里,或找到一个满足条件的边界。读本篇前先理解复杂度与数组。

本篇数值示例约定数组元素和目标均为有限数值;查找函数不修改输入。无序数组先考虑顺序查找;有序且可按下标访问的数组可以使用二分。如果只是查一次,不要忽略“先排序再二分”中的排序成本。

2. 顺序查找:逐个排除 ​

2.1 判断是否存在 ​

扫描到下标 i 时,前面的元素都已经确认不是目标。当前元素相等即可返回,否则继续;遍历结束仍没有匹配则返回 false。

js
function seqSearch(arr, data) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === data) return true;
    }
    return false;
}

空数组自然返回 false。这里返回布尔值;后面的二分函数返回下标,不要混淆两种接口。最好时间为 O(1),最坏为 O(n),辅助空间为 O(1)。

2.2 查找最小值与最大值 ​

非空数组用第一个元素初始化,避免将初始值设为零而误判全负数或全正数输入。本篇明确约定空数组返回 null;这是对旧示例隐式返回 undefined 的调整。

js
function findMin(arr) {
    if (arr.length === 0) return null;
    let min = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) min = arr[i];
    }
    return min;
}

function findMax(arr) {
    if (arr.length === 0) return null;
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

处理下标 i 之前,变量保存的是区间 [0, i) 内的最小值或最大值。每次比较扩展一个元素,直到覆盖全部数组。两个函数均为线性时间、常数辅助空间。

3. 二分查找:维护候选区间 ​

3.1 为什么可以排除一半 ​

前提是数组按非降序排列。当中间元素小于目标时,它左边的元素也不可能等于目标;因此可以排除中点及其左边。中间元素大于目标时同理排除右半部分。

本篇始终使用闭区间 [left, right]:如果目标存在,则至少有一个匹配还在候选区间内。初始化覆盖整个数组;循环中每次都移除已经检查的中点,保证区间严格缩小。

js
function binarySearch(arr, data) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] < data) {
            left = mid + 1;
        } else if (arr[mid] > data) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

返回一个匹配下标,无匹配返回 -1;重复元素存在时不保证返回第一个或最后一个。函数不在每次调用时扫描数组检查有序性,否则单次查询成本会变成线性;有序性由调用者保证。

3.2 最容易错的最后一个位置 ​

对 [1, 3, 5] 查找 5:第一次中点为 1,排除后得到 [2, 2]。此时仍有一个候选元素,必须再检查一次。

所以闭区间写 left <= right。如果误写为 left < right,单元素数组和某些首尾答案会漏查。空数组的初始区间为 [0, -1],循环不会进入。

最坏时间为 O(log n),辅助空间为 O(1)。二分法依赖范围可以被单调地排除,不适用于任意无序数据。

4. 变式:第一个不小于目标的位置 ​

在熟悉基本二分之后,再学习边界问题。为了保持区间约定一致,仍使用闭区间,额外用 answer 记录已找到的最靠左候选位置。

js
function lowerBound(arr, data) {
    let left = 0;
    let right = arr.length - 1;
    let answer = arr.length;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] >= data) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
}

找到满足条件的中点后继续往左寻找,不能立即返回。返回数组长度表示所有元素都小于目标,或数组为空;该值也可作为插入位置,但不能直接当作有效元素下标读取。

例如 [1, 2, 2, 4] 中查找 2 返回 1,查找 3 返回 3,查找 5 返回 4。时间与辅助空间仍分别为 O(log n)、O(1)。

5. 边界与验证 ​

用例基本二分的期望边界查找的期望
空数组,目标 2-10
[2],目标 200
[1, 3, 5],目标 522
[1, 3, 5],目标 4-12
[1, 2, 2, 4],目标 21 或 21

文档示例由仓库回归测试直接读取并执行,运行:

sh
node --test tests/algorithm-foundations-examples.test.mjs

先手推用例,再执行测试。学会之后关闭文章,重新写一遍,解释每一处加减 1 的理由。

6. 学到这里先停下 ​

第一轮掌握顺序查找、闭区间二分与一个边界变式即可。树结构查找放到树阶段;散列表查找放到学习路线的哈希阶段。插值查找与斐波那契查找作为选学,不保留只有标题却没有内容的章节。

下一步练习:将基本二分改为查找第一个相等的位置,并说明如何借助 lowerBound 判断目标是否确实存在。

评论

正在加载评论…