. . . . . . . . . . . . . . . . 154 10. 查找算法 155 10.1. 线性查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 10.2. 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 10.3. 哈希查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 10.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . 数据结构：常用的基本数据类型，数据在内存中的存储方式、数据结构分类方法。数组、链表、栈、队列、 散列表、树、堆、图等数据结构，内容包括定义、优劣势、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：查找算法、排序算法、搜索与回溯、动态规划、分治算法，内容包括定义、使用场景、优劣势、时 空效率、实现方法、示例题目等。 0. 写在前面 hello‑algo.com 2 Figure 0‑1. Hello

. . . . . . . . . . . . . . . . 157 10. 查找算法 158 10.1. 线性查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 10.2. 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 10.3. 哈希查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 10.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . 数据结构：常用的基本数据类型，数据在内存中的存储方式、数据结构分类方法。数组、链表、栈、队列、 散列表、树、堆、图等数据结构，内容包括定义、优劣势、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：查找算法、排序算法、搜索与回溯、动态规划、分治算法，内容包括定义、使用场景、优劣势、时 空效率、实现方法、示例题目等。 0. 写在前面 hello‑algo.com 2 Figure 0‑1. Hello

10.1 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 10.2 二分查找插入点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 10.3 二分查找边界 . . 位于 ? 之后，所以排除字典前半部分，查找范围缩小到后半部分。 3. 不断重复步骤 1. 和 步骤 2. ，直至找到拼音首字母为 ? 的页码为止。 图 1‑1 查字典步骤 查字典这个小学生必备技能，实际上就是著名的“二分查找”算法。从数据结构的角度，我们可以把字典视 为一个已排序的“数组”；从算法的角度，我们可以将上述查字典的一系列操作看作“二分查找”。 例二：整理扑克。我们在打牌时，每 将数据结构存储在内存中，同时编写代码调用 CPU 和 GPU 执行算法。这样一来，我们就能把生活中的问题 转移到计算机上，以更高效的方式解决各种复杂问题。 � 如果你对数据结构、算法、数组和二分查找等概念仍感到一知半解，请继续往下阅读，本书将 引导你迈入数据结构与算法的知识殿堂。 1.2 算法是什么 1.2.1 算法定义 「算法 algorithm」是在有限时间内解决特定问题的一组指令或操作步骤，它具有以下特性。

大到一个国家，小 到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下； 羽毛球筒则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。 本书旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通 过编程来实现它们。在此基础上，本书致力于揭示算法在复杂世界中的生动体现，展现算法之美。希望本书 10.1 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 10.2 二分查找插入点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 10.3 二分查找边界 . . 位于 ? 之后，所以排除字典前半部分，查找范围缩小到后半部分。 3. 不断重复步骤 1. 和 步骤 2. ，直至找到拼音首字母为 ? 的页码为止。 图 1‑1 查字典步骤 查字典这个小学生必备技能，实际上就是著名的“二分查找”算法。从数据结构的角度，我们可以把字典视 为一个已排序的“数组”；从算法的角度，我们可以将上述查字典的一系列操作看作“二分查找”。 例二：整理扑克。我们在打牌时，每

10.1 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 10.2 二分查找插入点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 10.3 二分查找边界 . . 例一：查阅字典。在字典里，每个汉字都对应一个拼音，而字典是按照拼音字母顺序排列的。假设我们需要 查找一个拼音首字母为 ? 的字，通常会按照图 1‑1 所示的方式实现。 1. 翻开字典约一半的页数，查看该页的首字母是什么，假设首字母为 ? 。 2. 由于在拼音字母表中 ? 位于 ? 之后，所以排除字典前半部分，查找范围缩小到后半部分。 3. 不断重复步骤 1. 和 步骤 2. ，直至找到拼音首字母为 图 1‑1 查字典步骤 第 1 章 初识算法 hello‑algo.com 11 查阅字典这个小学生必备技能，实际上就是著名的二分查找算法。从数据结构的角度，我们可以把字典视为 一个已排序的“数组”；从算法的角度，我们可以将上述查字典的一系列操作看作是“二分查找”。 例二：整理扑克。我们在打牌时，每局都需要整理扑克牌，使其从小到大排列，实现流程如图 1‑2 所示。 1. 将扑克牌划分为“有

. . . . . . . . . . . . . 182 10. 搜索 184 10.1. 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 10.2. 二分查找边界 . . . . . . . . . . . . . . . . . . . . . . . . . 例一：查阅字典。在字典里，每个汉字都对应一个拼音，而字典是按照拼音的英文字母顺序排列的。假设我 们需要查找一个拼音首字母为 ? 的字，通常会这样操作： 1. 翻开字典约一半的页数，查看该页首字母是什么，假设首字母为 ? 。 2. 由于在英文字母表中 ? 位于 ? 之后，所以排除字典前半部分，查找范围缩小到后半部分。 3. 不断重复步骤 1‑2 ，直至找到拼音首字母为 ? 的页码为止。 1. 初识算法 初识算法 hello‑algo.com 8 Figure 1‑1. 查字典步骤 查阅字典这个小学生必备技能，实际上就是著名的「二分查找」。从数据结构的角度，我们可以把字典视为一 个已排序的「数组」；从算法的角度，我们可以将上述查字典的一系列操作看作是「二分查找」算法。 例二：整理扑克。我们在打牌时，每局都需要整理扑克牌，使其从小到大排列，实现流程如下： 1. 将扑克牌划分为“有序”和“无序”两部分，并假设初始状态下最左

大到一个国家，小 到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下； 羽毛球筒则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。 本书旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通 过编程来实现它们。在此基础上，本书致力于揭示算法在复杂世界中的生动体现，展现算法之美。希望本书 10.1 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 10.2 二分查找插入点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 10.3 二分查找边界 . . 位于 ? 之后，所以排除字典前半部分，查找范围缩小到后半部分。 3. 不断重复步骤 1. 和步骤 2. ，直至找到拼音首字母为 ? 的页码为止。 图 1‑1 查字典步骤 查字典这个小学生必备技能，实际上就是著名的“二分查找”算法。从数据结构的角度，我们可以把字典视 为一个已排序的“数组”；从算法的角度，我们可以将上述查字典的一系列操作看作“二分查找”。 例二：整理扑克。我们在打牌时，每

可以自动保存代码，至少在每次编译前都会保存。 3. 可以显示代码所在的行数。 4. 拥有较好的项目文件纵览和导航能力，可以同时编辑多个源文件并设置书签，能够匹配括号，能够跳 转到某个函数或类型的定义部分。 5. 完美的查找和替换功能，替换之前最好还能预览结果。 6. 可以注释或取消注释选中的一行或多行代码。 7. 当有编译错误时，双击错误提示可以跳转到发生错误的位置。 8. 跨平台，能够在 Linux、Mac OS 如果包名不是以 . 或 / 开头，如 "fmt" 或者 "container/list" ，则 Go 会在全局文件进行查找；如果 包名以 ./ 开头，则 Go 会在相对目录中查找；如果包名以 / 开头（在 Windows 下也可以这样使 用），则会在系统的绝对路径中查找。 导入包即等同于包含了这个包的所有的代码对象。 除了符号 _ ，包中所有代码对象的标识符必须是唯一的，以避免名称冲突。但是相同的标识符可以在不同 计算过的。即每个更后面的数都是基于之前计算结果的重复计算，正如示例 6.11 fibonnaci.go 所展示的 那样。 而我们要做就是将第 n 个数的值存在数组中索引为 n 的位置（详见第 7 章），然后在数组中查找是否已 经计算过，如果没有找到，则再进行计算。 程序 Listing 6.17 - fibonacci_memoization.go 就是依照这个原则实现的，下面是计算到第 40 位数字的 性能对比：

可以自动保存代码，至少在每次编译前都会保存。 3. 可以显示代码所在的行数。 4. 拥有较好的项目文件纵览和导航能力，可以同时编辑多个源文件并设置书签，能够匹配括号，能够跳转到某个函 数或类型的定义部分。 5. 完美的查找和替换功能，替换之前最好还能预览结果。 6. 可以注释或取消注释选中的一行或多行代码。 7. 当有编译错误时，双击错误提示可以跳转到发生错误的位置。 8. 跨平台，能够在 Linux、Mac OS 或 / 开头，如 "fmt" 或者 "container/list" ，则 Go 会在全局文件进行查找；如 果包名以 ./ 开头，则 Go 会在相对目录中查找；如果包名以 / 开头（在 Windows 下也可以这样使 用），则会在系统的绝对路径中查找。 导入包即等同于包含了这个包的所有的代码对象。 除了符号 _ ，包中所有代码对象的标识符必须是唯一的，以避 您可以同时测试多个可能符合条件的值，使用逗号分割它们，例如： case val1, val2, val3 。 每一个 case 分支都是唯一的，从上至下逐一测试，直到匹配为止。（ Go 语言使用快速的查找算法来测试 switch 条件与 case 分支的匹配情况，直到算法匹配到某个 case 或者进入 default 条件为止。） 一旦成功地匹配到某个分支，在执行完相应代码后就会退出整个 switch

大到一個國家，小 到一個家庭，社會的主要組織形式呈現出“樹”的特徵；冬天的衣服就像“堆疊”，最先穿上的最後才能脫下； 羽毛球筒則如同“佇列”，一端放入、一端取出；字典就像一個“雜湊表”，能夠快速查找目標詞條。 本書旨在透過清晰易懂的動畫圖解與可執行的程式碼範例，使讀者理解演算法和資料結構的核心概念，並能 夠透過程式設計來實現它們。在此基礎上，本書致力於揭示演算法在複雜世界中的生動體現，展現演算法之 雜湊衝突 load factor 负载因子 負載因子 separate chaining 链式地址 鏈結位址 open addressing 开放寻址 開放定址 linear probing 线性探测 線性探查 lazy deletion 懒删除 懶刪除 binary tree 二叉树 二元樹 tree node 树节点 樹節點 left‑child node 左子节点 左子節點 right‑child list 邻接表 鄰接表 breadth‑first search 广度优先搜索 廣度優先搜尋 depth‑first search 深度优先搜索 深度優先搜尋 binary search 二分查找 二分搜尋 searching algorithm 搜索算法 搜尋演算法 sorting algorithm 排序算法 排序演算法 selection sort 选择排序 選擇排序 bubble