算法入门：从猜数字游戏说起

假设这样一个场景：你的朋友心里想了一个1到100之间的整数，你的任务是猜出这个数字是多少。每次猜测后，朋友会告诉你猜得“太大”、“太小”还是“正好”。你会怎么猜？

大多数人可能会说“从1开始，一个一个往上猜”。这确实是个合理的方法——如果朋友想的数字是37，你就从1开始猜，1太小，2太小……一直猜到37，正好猜中。这种方法简单直接，不需要动太多脑筋。

但让我们仔细算一算：如果朋友想的是100，你可能需要猜100次才能得到答案。100次！这听起来有点多了。有没有更快的方法？

有的。你可以把数字范围从中间分开，第一次直接猜50。朋友如果说“太小”，你立刻知道答案在51到100之间；如果说“太大”，答案就在1到49之间。无论哪种情况，你的搜索范围瞬间缩小了一半。第二次再从新范围的中间猜，又缩小一半……按照这种方式，最多只需要7次就能锁定任何1到100之间的数字。

从100次到7次——同样是猜数字游戏，效率提升了十几倍。这就是算法优化的力量，也是整个计算机科学世界的核心追求。

从直觉到策略：两种搜索思路的对比

让我们更正式地描述这个问题。假设目标数字是$T$，范围是1到$n$之间的整数。每次猜测$g$后，会得到三种可能的反馈：

• $T < g$：目标比猜测小
• $T > g$：目标比猜测大
• $T = g$：猜中了

用线性查找的策略，我们假设一个可能很小的范围（比如1到10），来看看整个过程：

``` 猜测 1 → 太大？(不对) → 猜 2 → 太大？(不对) → 猜 3 → ... → 猜 10 ```

这种逐个枚举的方式，时间复杂度是$O(n)$——问题规模增长多少，所需时间就线性增长多少。对于$n=100$，需要100次；对于$n=1,000,000$，就需要一百万次。这个增长速度是线性的，画成曲线的话是一条倾斜向上的直线。

现在看二分查找的策略：

``` 第 1 次：猜 50 → 范围 [1,49] 或 [51,100] → 范围缩小到 50 第 2 次：猜 25 → 范围缩小到 25 第 3 次：猜 13 → 范围缩小到 13 第 4 次：猜 7 → 范围缩小到 7 第 5 次：猜 4 → 范围缩小到 4 第 6 次：猜 2 → 范围缩小到 2 第 7 次：猜 1 → 找到答案 ```

这个过程的关键特征是：每猜测一次，搜索范围就减少一半。数学上，这对应着对数函数的性质。对于范围1到$n$，所需猜测次数恰好是$\lceil \log_2 n \rceil$。当$n=100$时，$\log_2 100 \approx 6.64$，向上取整就是7次。当$n$增长到一百万时，$\log_2 1,000,000 \approx 19.93$，仍然只需要约20次。

这就是$O(\log n)$时间复杂度的威力——即使面对海量数据，所需时间也只是缓慢增长。当$n$从100增长到100万（增长一万倍），所需猜测次数只从7次增长到20次（不到三倍）。

对数函数$\log_2 n$的增长有多慢？可以看这个对比：线性函数$n$增长到原来的10倍时，时间变成10倍；但对数函数$\log_2 n$增长到原来的10倍时，$n$增长到$2^{10} = 1024$倍。换句话说，数据规模扩大一千倍，二分查找只需要多猜测10次。这是一种“超线性”的效率提升——数据越多，二分查找相对线性查找的优势就越明显。

为什么是“二分”：理解算法的核心思想

你可能会问：为什么一定要从中间开始猜？如果第一次猜25或75，范围也能缩小很多啊。

这确实是个好问题。仔细想想：无论你第一次猜哪个数字，比如猜25，如果答案比25大，那搜索范围变成26到100（75个数字）；如果答案比25小，搜索范围变成1到24（24个数字）。这两种情况的平均值是$(75 + 24) / 2 = 49.5$。

如果第一次猜50呢？缩小后的范围要么是1到49（49个数字），要么是51到100（50个数字），平均值是$(49 + 50) / 2 = 49.5$。

从这个角度看，猜任何数字的“平均缩小效果”是一样的！这似乎意味着选择哪个数字无关紧要。

但这里有个关键区别：我们关心的是最坏情况的表现。在最坏情况下（也就是运气最差、目标数字恰好在更难找的位置），二分查找的策略能够保证最优的性能。从中间分开，确保无论目标在哪里，搜索范围都“尽可能均匀”地缩小。

这引出了一个重要的算法设计思想：平衡。二分查找之所以高效，正是因为它在每一步都保持搜索范围的“平衡”，避免出现极端的不均匀情况。类似的平衡思想在后续章节中会遇到很多——平衡二叉树、负载均衡、分治策略中的子问题划分……

当然，在实际工程中，策略的选择还会受到其他因素影响：

• **数据分布不均匀时**：如果已知目标数字更可能在某些区间，可以调整猜测策略
• **有历史信息时**：如果朋友之前玩过这个游戏，记住他的偏好可以加快猜测
• **需要找多个目标时**：同时维护多个候选区间可能更高效
• **有并发需求时**：多个猜测者同时进行可以加速搜索

这些扩展思考告诉我们：算法的基本原理是通用的，但具体应用时需要结合实际约束进行调整。这正是问题驱动学习方法的核心——不是死记硬背某种“标准解法”，而是从问题本身出发，灵活运用算法思想。

数学视角：信息论与算法复杂度

从数学角度，二分查找的神奇效率可以用信息论来解释。1948年，香农（Claude Shannon）在他的开创性论文《通信的数学原理》中提出了信息熵的概念，奠定了现代信息论的基础。

信息论的核心观点是：信息是用来消除不确定性的。一次二元比较（“是/否”，“太大/太小”）能够提供恰好1比特的信息。如果某个问题的答案有$n$种可能性，你需要获取足够的信息来消除这$n$种不确定性。

对于1到100之间的数字，答案有100种可能性，需要的信息量是$\log_2 100 \approx 6.64$比特。由于每次猜测只能提供1比特信息，理论上至少需要7次比较才能确定答案。二分查找恰好达到了这个理论下界——它是一种信息论最优的算法。

这就是理解算法的一个重要视角：理论下界。每一种计算问题都有其固有的难度，算法设计的目标是尽可能接近这个下界。二分查找之所以重要，不仅因为它本身高效，更因为它证明了对于有序数组的查找问题，$O(\log n)$已经是理论上能达到的最佳时间复杂度——没有算法能比它更好了。

用更形式化的语言说：对于长度为$n$的有序数组，在最坏情况下，任何基于比较的查找算法都需要$\Omega(\log n)$次比较。这个结论来自于比较树模型（decision tree model）的分析——$n$个不同元素的不同排列结果至少有$n!$种，而高度为$h$的二叉树最多只能有$2^h$个叶子，所以必须满足$2^h \geq n!$，即$h \geq \log_2 (n!) = \Omega(n \log n)$。不过对于查找问题，我们只需要找到特定元素的位置，所以分析更为直接。

这种理论分析的方法在算法学习中非常重要。它帮助我们回答“还能更好吗”这个问题——如果已经达到理论下界，就不应该再徒劳地寻找更快的算法，而应该把精力放在其他方面，比如优化常数因子、降低空间复杂度，或者改进平均情况而非最坏情况的性能。

从猜数字到算法世界：一幅知识地图

猜数字游戏只是算法世界的冰山一角。让我们以这个问题为出发点，鸟瞰整个算法与数据结构领域。

如果把算法比作解决问题的“方法库”，这个库中有许多针对不同问题的工具：

查找问题是直接延伸自猜数字的领域。除了二分查找，还有线性查找、二叉搜索树查找、哈希表查找、B树范围查找、跳表查找等。不同的数据结构支撑不同的查找算法：有序数组支持二分查找，二叉搜索树支持对数级查找，哈希表支持常数级查找（尽管要处理哈希冲突）。选择哪种查找方案，取决于数据的特性和查询的需求。

排序问题是另一个经典领域。给定$n$个数字，如何按从小到大的顺序排列它们？冒泡排序和选择排序的时间复杂度是$O(n^2)$，而归并排序和快速排序只需要$O(n \log n)$。更令人惊讶的是，$O(n \log n)$已经是比较排序的理论下界——这意味着在比较排序的世界里，归并排序和快速排序已经接近最优。计数排序、桶排序等非比较排序算法则可以在某些特定条件下突破这个限制，达到线性时间复杂度。

图算法处理更复杂的关系结构。当数据之间不是简单的线性关系，而是形成了错综复杂的网络时，图算法就派上用场了。社交网络中的朋友推荐、最短路径规划、任务调度、网络流优化——这些问题的背后都是图算法的身影。

字符串算法处理文本数据的匹配和搜索。当你在搜索引擎中输入关键词时，后台可能在运行复杂的字符串匹配算法。在生物信息学中，字符串算法用于DNA序列比对；在编译器设计中，它们用于语法分析。

最优化问题寻找“最好”的方案。旅行商问题（TSP）寻求访问所有城市的最短路线，背包问题在容量限制下最大化价值，这些问题的解决方案在物流、金融、工程等领域有广泛应用。

机器学习算法则从数据中自动学习规律。从简单的线性回归到复杂的深度神经网络，机器学习算法正在改变各行各业的面貌。

后续章节会逐一深入这些领域，每一章都以一个具体问题为起点，分析为什么需要新的算法，理解新算法的核心思想，掌握其实现方法，并探讨其局限性。

追问“是什么”，更追问“为什么”

回到猜数字游戏。我们已经知道二分查找比线性查找高效，但这种“知道”是表面的。真正的理解需要回答更深层的问题：

为什么二分查找是高效的？因为它充分利用了“有序”这个信息——每次比较都能排除一半的候选数字。

为什么每次排除一半就足够快？因为对数函数的增长极为缓慢。即使数据规模增长一千倍，所需时间只增加几倍。

为什么从中间分开就足够了？因为这样能保证搜索范围“均匀”缩小，最坏情况下也能保持最优性能。

为什么不能更快？因为信息论告诉我们，确定一个$n$选1的问题至少需要$\log_2 n$比特的信息，二分查找已经达到了这个下界。

这种不断追问的方式，是培养算法思维的关键。当你遇到一个新算法时，不要满足于“它是什么”或“怎么用”，而要追问“为什么这样设计”、“背后的原理是什么”、“还能进一步优化吗”。

这种追问不仅帮助理解单个算法，更重要的是，它帮助你建立起算法设计的“直觉”。当你面对一个全新的问题时，这种直觉会告诉你从哪个方向思考、使用什么工具、避免什么陷阱。

费曼（Richard Feynman）有句名言：“我不能创造的东西，我就不能理解。”（What I cannot create, I do not understand.）这句话用在算法学习上再合适不过。如果你只是机械地记忆某个算法的代码，而没有理解它为什么有效，那你并没有真正学会这个算法。真正理解一个算法，意味着你能够在没有参考资料的情况下，从基本原理出发重新推导出它。

当然，这不是说要死记硬背推导过程，而是说当你需要的时候，能够独立思考出解决方案。理解原理让你知道什么时候该用什么算法，以及如何根据具体问题调整算法。

追问“还能更好吗”：持续优化的思维方式

解决了问题并不等于完成了工作。算法学习中另一个重要的思维方式是：永远问“还能更好吗”。

对于猜数字游戏，我们已经知道二分查找是最优的——至少在标准的“猜数字”场景下。但这不意味着追问的结束：

• **如果猜测次数被限制为4次怎么办？** 这时候二分查找可能无法保证一定找到答案，需要权衡猜测策略
• **如果数字会动态变化怎么办？** 静态的二分查找不再适用，可能需要更复杂的追踪机制
• **如果需要同时找多个数字怎么办？** 可以考虑批量查找或并行搜索
• **如果允许撒谎（错误反馈）怎么办？** 需要引入容错机制和冗余猜测

每一种新的约束条件，都可能催生新的算法或算法变体。这种“约束驱动”的创新思维，是算法发展的重要动力。

在后续章节中，我们会看到很多这样的例子：

• **排序算法的演进**：从$O(n^2)$的简单排序到$O(n \log n)$的高效排序，再到针对特殊数据（近乎有序、范围受限等）的线性排序
• **查找数据结构的演进**：从数组到链表，从二叉搜索树到平衡树，从哈希表到布隆过滤器
• **图算法的演进**：从朴素的最短路径到Dijkstra算法，再到A*启发式搜索

每一次演进，都源于对现有方案的“不满足”，以及对“还能更好吗”的持续追问。

这种思维方式的重要性在于：实际工作中的问题往往没有标准答案。教科书上的经典问题是“理想化”的，而真实场景充满各种约束和tradeoff。只有具备持续优化的意识，才能在复杂环境中找到真正合适的解决方案。

学习框架：问题驱动与深度思考

现在，我们可以总结一下本书倡导的核心学习框架：

第一步：明确问题 从具体的应用场景出发，理解要解决的核心问题是什么。问题驱动，而不是理论驱动。

第二步：提出朴素方案 先用最直觉的方法解决，感受问题本身的特点和难点。朴素方案往往暴露出改进的方向。

第三步：分析问题本质 追问：这个问题的核心困难是什么？有哪些可以利用的信息/结构/约束？理论下界是什么？

第四步：设计改进方案 基于对问题本质的理解，设计更高效的算法。思考是否有现成的算法模式可以借鉴（如分治、动态规划、贪心等）。

第五步：复杂度分析 从时间复杂度和空间复杂度两个维度分析改进效果，验证是否达到预期目标。

第六步：考虑边界情况 测试边界条件（空输入、极端数据、重复元素等），确保算法的正确性和健壮性。

第七步：实现与验证 用代码实现算法，通过实际测试验证效果。注意实现细节：整数溢出、递归深度、内存管理等。

第八步：反思与扩展 这个算法可以推广吗？有什么局限性？在什么情况下会退化？能否进一步优化？

这个框架强调的是主动思考而非被动接受。每一章的内容都会按照这个框架展开，帮助你建立系统化的算法思维。

从局部到全局：算法知识的融会贯通

学习算法的一个常见困难是：知识点太多，容易碎片化。刚学完二分查找，又来了归并排序；归并排序还没消化，又冒出了动态规划。这些知识点看起来互不相关，难以形成整体认知。

其实，算法的世界远没有看起来那么碎片化。大多数经典算法都共享一些核心思想，理解这些思想能够帮助我们将零散的知识点串联起来。

分治思想（Divide and Conquer）是其中最重要的之一。它的核心思想是：将大问题分解为若干小问题，分别解决后再合并结果。

• 二分查找是分治思想的直接应用：每次将搜索范围一分为二
• 归并排序也是分治思想：先递归排序左半部分和右半部分，再合并两个有序子数组
• 快速排序同样运用分治：将数组分为小于基准和大于基准的两部分，分别排序

三种看似不同的算法，骨子里都是“分而治之”。一旦理解了这个共性，就不需要分别记忆三个算法的细节——你可以从一个例子出发，理解分治的核心，自然而然地推导出各种变体。

递归与迭代是另一个贯穿全书的主题。递归提供了一种自然的思考方式（将大问题分解为同类小问题），而迭代则往往是更高效的执行方式。许多算法的递归版本容易理解，迭代版本则需要更多思考。这种递归与迭代的转换，是算法实现中的重要技巧。

复杂度分析则是一套通用的评估语言。$O(n)$、$O(n \log n)$、$O(n^2)$这些符号帮助你快速判断算法的scalability（可扩展性），比较不同方案的优劣，指导技术选型。后续章节中，我们会不断运用这套语言分析各种算法的性能。

数据结构与算法的关系也值得强调。算法离不开数据结构作为支撑：二分查找需要有序数组作为底层存储，归并排序需要能够高效分割和合并的存储结构，图算法需要图结构的表示方式。选择合适的数据结构，往往是优化算法的关键一步。

后续章节会详细讨论各种数据结构：数组、链表、栈、队列、哈希表、树、堆、图等。每种数据结构都有其特点和适用场景，理解它们是成为算法高手的必经之路。

二分查找的变体与延伸

作为本章的最后一个技术话题，让我们深入探讨二分查找的一些变体，这些变体在后续章节中会再次出现。

查找第一个等于目标的位置：如果数组中可能有重复元素，如何找到第一个出现的位置？思路是：即使$nums[mid] == target$，也要继续在左半部分搜索，直到$low == high$。

查找最后一个等于目标的位置：类似地，如果要找最后一个出现的位置，即使$nums[mid] == target$，也要继续在右半部分搜索。

查找第一个大于等于目标的位置：这在“寻找插入位置”等场景中很有用。稍微修改比较条件即可实现。

查找最后一个小于等于目标的位置：是上一个变体的镜像版本。

旋转数组中的查找：如果有序数组被“旋转”了（比如$[0,1,2,4,5,6,7]$变成$[4,5,6,7,0,1,2]$），二分查找需要更复杂的处理——因为有一半是“有序但被旋转”的。每次比较后，需要判断哪一半是有序的，然后决定在有序半部分搜索还是去另一半搜索。

这些变体展示了二分查找思想的强大之处：核心思想简单（每次缩小搜索范围），但可以根据具体需求灵活调整。

本章小结与下章预告

本章从猜数字游戏出发，带领大家初探算法世界。我们学到了：

1. 线性查找与二分查找的对比：从$O(n)$到$O(\log n)$，效率提升是指数级的 2. 信息论视角：二分查找达到了查找问题的理论下界 3. 追问“为什么”的重要性：理解算法原理，而非死记硬背 4. 追问“还能更好吗”的思维方式：持续优化，不断突破 5. 算法学习的核心框架：问题驱动、深度思考、理论分析与实践验证并重 6. 算法世界的全景概览：查找、排序、图、字符串、最优化……各领域既相对独立，又通过共同思想相互联系

下一章我们将深入排序算法的世界。排序是最基础也最经典的算法问题之一，看似简单的“把一堆数字排好序”背后，蕴含着丰富的算法思想和技巧。我们会看到从$O(n^2)$到$O(n \log n)$的演进之路，理解为什么$O(n \log n)$是比较排序的理论极限，以及如何突破这个限制。

在开始下一章之前，建议你花点时间思考这几个问题：

• 如果数据基本有序（只有少数几个元素不在正确位置），哪种排序算法会特别高效？
• 如果内存极其有限，无法一次性加载所有数据，该如何排序？
• 如果要排序的对象不是数字，而是自定义的比较规则呢？

带着这些问题进入下一章，你会发现排序算法的世界比想象中更加精彩。

算法的学习是一场漫长的旅程。从猜数字游戏到复杂的数据处理系统，从课堂上的经典问题到工业界的实际应用，算法思维无处不在。下一章开始，我们将正式踏上这段旅程，深