每个系列一本前端好书，帮你轻松学重点。

本系列来自上海交通大学硕士，华为高级算法工程师 靳宇栋 的 《Hello，算法》

众里寻他千百度，深度遍历二叉树。

踏破铁鞋无觅处，广度优先无向图。

—— 《七言绝句》灵感~

话题向下展开之前，先聊个我们都玩过的游戏：猜数字。

一方出数字，另一方猜。猜的时候，我们希望对方不只是给一个“对”或“错”的结果，而是能给出答案的相对大小，这样就可以通过逐步缩小范围来更快定位到最终答案。

这其实就是一个有关搜索的典型案例。

何为“搜索”

这是个不太需要解释的东西，百度搜索，业务数据搜索，不论是精准搜索，还是范围搜索，在日常需求中都十分常见。

搜索的过程是在数据结构中找到一个或一组满足特定条件的元素。

根据实现思路分为以下两类。

• 遍历定位，如数组、链表、树和图的遍历等。
• 利用数据结构或数据包含的先验信息，高效查找，如二分查找、哈希查找和二叉搜索树查找等。

猜数字采用的就是“二分查找”法，我们先来认识一下它。

二分查找

二分查找是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素，或搜索区间为空。

通过一道题感受一下：

给定一个长度为 n 的数组 nums ，从小到大排列，且不重复，查找并返回元素 target 在该数组中的索引，若数组不包含该元素，则返回 -1。

解题思路：

1、拟定初始索引区间

2、计算中点索引

3、比较目标值与中点值的相对大小，决定下一步是向前算，还是向后算

4、重复以上3步

代码实现：

/* 二分查找（双闭区间） */
function binarySearch(nums, target) {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    let i = 0,
        j = nums.length - 1;
    // 循环，当搜索区间为空时跳出（当 i > j 时为空）
    while (i <= j) {
        // 计算中点索引 m ，使用 parseInt() 向下取整
        const m = parseInt(i + (j - i) / 2);
        if (nums[m] < target)
            // 此情况说明 target 在区间 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target)
            // 此情况说明 target 在区间 [i, m-1] 中
            j = m - 1;
        else return m; // 找到目标元素，返回其索引
    }
    // 未找到目标元素，返回 -1
    return -1;
}

优点与局限

二分查找在时间和空间方面都有较好的性能。

• 时间效率高。当数据大小 n = 220 时，线性查找需要 220 轮循环，二分查找仅需 20 轮。
• 相较于需要额外空间的搜索算法，更省空间。

然而，它并非适用所有情况，主要有以下原因。

• 若数据无序，要先进行排序，得不偿失。
• 二分查找需要跳跃式（非连续地）访问元素，而在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构。
• 当数据量 n 较小时，线性查找需要做的操作和判断更少，反而比二分查找更快。

尽管二分查找存在不足，但更为不足的是人的思维，能用上二分查找已经可以被列入“聪明”范畴了。

通常，人们下意识的选择还是暴力搜索。

暴力搜索

暴力搜索指通过遍历来定位目标。同样是遍历，在“线性”和“非线性”的数据结构中又有所区别。

1、线性搜索

适用于数组和链表等线性结构。

它从数据结构的一端开始，逐个访问元素，直到找到目标元素，或到达另一端仍没有找到目标元素为止。

2、优先搜索

适用于图和树等非线性结构，又分为“广度优先”和“深度优先”。

广度优先搜索从初始节点开始逐层搜索，由近及远地访问各个节点。

深度优先搜索从初始节点开始，沿着一条路径走到头，再回溯并尝试其他路径，直到遍历完整个数据结构。

暴力搜索的优点是简单且通用性好，无须对数据做预处理和借助额外的数据结构。

但是，此类算法的时间复杂度为O(n) ，数据量越大，性能劣化越明显。

自适应搜索

自适应搜索指利用数据的特有属性（例如有序性）来优化搜索过程，从而更高效地定位目标元素。

除了上面介绍的“二分查找”，自适应类型的搜索还有：

• 哈希查找：利用哈希表将搜索数据和目标数据建立为键值对映射，实现查询操作。
• 树查找：在特定的树结构（例如二叉搜索树）中，基于比较节点值来快速排除节点，从而定位目标元素。

自适应搜索的优点是效率高，时间复杂度可达到 O(logn) 甚至 O(1) 。

然而，使用这些算法往往需要对数据进行预处理。

例如，二分查找需要预先对数组进行排序，哈希查找和树查找都需要借助额外的数据结构，维护这些数据结构也需要额外的时间和空间开销。

鉴于以上，实现搜索类需求不是没有方案，而是方案很多，这就引出了方案选择的问题。

方案选择

评定算法优劣的维度通常分为：时间和空间。

但具体到实际需求，还取决于规模、性能要求、数据查询与更新频率等。

使用哪一种需要根据方案的特点来定夺，简要介绍供参考：

线性搜索： 通用性较好，无须预处理，适用体量较小，更新频率较高的数据。

二分查找： 数据量适中，有序，更新频率低。

哈希查找： 数据量适中，对查询性能要求高的无序数据。

树查找： 海量，有序，范围查找。

小结

搜索需求应用广泛，可能涉及的数据量级和数据结构都会不同，没有通解，做决策需要一定知识广度。

本篇只作为引子，有个大概的认识，各位在项目中落地仍要分门别类进行拓展，一起加油！~

更多好文第一时间接收，可关注公众号：“前端说书匠”