Hello 算法深度解析二分查找的原理、双闭区间与左闭右开区间实现对比【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo二分查找binary search是《Hello 算法》搜索章节最基础的算法之一它建立在数据有序这一前提之上通过每轮将搜索区间减半的方式把查找的时间复杂度从线性降到对数级。本文以仓库中 日本语版二分查找文档与中文版 binary_search.md 同源为主体骨架结合 codes 下 Python、Java、Go、C 等多语言实现源码完整讲解双闭区间与左闭右开区间两种写法的异同、中点溢出问题的成因以及二分查找的适用边界。读完后你将能够徒手写出无 Bug 的二分查找并能针对不同区间定义准确推导循环条件与指针移动规则。问题定义在有序数组中定位目标文章开篇提出了一道经典面试题给定长度为 $n$ 的数组nums元素按从小到大排列且不重复若目标元素target存在于数组中则返回其索引否则返回 $-1$。以仓库中多个语言的测试用例为例如 binary_search.py 与 binary_search.java采用的统一示例为nums [1, 3, 6, 8, 12, 15, 23, 26, 31, 35] target 6 # 正确结果为索引 2对该问题的直观解法是线性扫描最坏情况下要比较 $n$ 次。而二分查找利用了有序 随机访问两个性质把每一轮的候选范围缩小一半因此得名 binary search。双闭区间写法算法主流程双闭区间 $[i, j]$ 表示左边界 $i$ 与右边界 $j$ 均被包含在搜索范围内。流程如下。初始化与循环结构初始化指针 $i 0$、$j n - 1$分别指向数组首元素与尾元素代表搜索区间 $[0, n-1]$。重复执行以下两步直到区间为空计算中点索引 $m \lfloor (i j) / 2 \rfloor$$\lfloor \rfloor$ 表示向下取整比较nums[m]与targetnums[m] target目标在右半区 $[m 1, j]$令 $i m 1$nums[m] target目标在左半区 $[i, m - 1]$令 $j m - 1$nums[m] target命中返回索引 $m$。若区间缩至为空仍未命中返回 $-1$。值得强调的是空区间的判定双闭区间下当 $i j$ 时区间才为空因此循环继续条件写作while (i j)。这是初学者最容易写错的地方——一旦把条件误写成i j就会漏掉 $i j$ 时边界元素仍可能等于target的情况。中点计算与整数溢出陷阱文中特别指出一个容易被忽略的细节$i$ 与 $j$ 都是int类型当数组极大时$i j$ 可能超出int的表示范围。为避免大数溢出通常改用等价形式$$m \lfloor i (j - i) / 2 \rfloor$$这一防溢出写法在仓库源码中得到了统一贯彻例如 binary_search.java 中的int m i (j - i) / 2;、binary_search.go 中的m : i (j-i)/2以及 binary_search.c 中的int m i (j - i) / 2;。而 binary_search.py 因为 Python 整数可无限增长仅受内存限制直接使用m (i j) // 2即可注释中也明确说明了这一语言差异。双闭区间参考实现以 Python 为例完整可运行代码见 binary_search.pydef binary_search(nums: list[int], target: int) - int: 二分查找双闭区间 # 初始化双闭区间 [0, n-1] 即 i, j 分别指向数组首元素、尾元素 i, j 0, len(nums) - 1 # 循环当搜索区间为空时跳出当 i j 时为空 while i j: m (i j) // 2 # 计算中点索引 m if nums[m] target: i m 1 # 此情况说明 target 在区间 [m1, j] 中 elif nums[m] target: j m - 1 # 此情况说明 target 在区间 [i, m-1] 中 else: return m # 找到目标元素返回其索引 return -1 # 未找到目标元素返回 -1各语言文件结构完全一致均同时包含两个区间版本的实现可直接对照学习语言文件路径Pythoncodes/python/chapter_searching/binary_search.pyJavacodes/java/chapter_searching/binary_search.javaGocodes/go/chapter_searching/binary_search.goCcodes/c/chapter_searching/binary_search.cCcodes/cpp/chapter_searching/binary_search.cppTypeScriptcodes/typescript/chapter_searching/binary_search.ts原文档中的 binary_search_step1.png 至 binary_search_step7.png 七张分步图完整演示了在示例数组上从区间 $[0, 9]$ 逐步收缩到命中索引 2 的全过程阅读时建议配合动画逐帧核对指针 $i$、$j$ 与中点 $m$ 的变化。复杂度分析时间复杂度 $O(\log n)$每轮循环区间减半最多执行 $\log_2 n$ 轮与数据规模呈对数关系。空间复杂度 $O(1)$算法仅使用 $i$、$j$、$m$ 三个指针无需任何与 $n$ 相关的额外空间。区间的另一种表示左闭右开除双闭区间外还有一种常见表示是左闭右开区间 $[i, j)$左端包含、右端不包含。此时区间 $[i, j)$ 在 $i j$ 时为空。两种写法在初始化、循环条件与收缩操作上存在三处系统性差异对比图见下以同仓库 binary_search.py 的左闭右开实现为例def binary_search_lcro(nums: list[int], target: int) - int: 二分查找左闭右开区间 # 初始化左闭右开区间 [0, n) 即 i, j 分别指向数组首元素、尾元素1 i, j 0, len(nums) # 循环当搜索区间为空时跳出当 i j 时为空 while i j: m (i j) // 2 # 计算中点索引 m if nums[m] target: i m 1 # 此情况说明 target 在区间 [m1, j) 中 elif nums[m] target: j m # 此情况说明 target 在区间 [i, m) 中 else: return m return -1两版差异可归纳为下表对比维度双闭区间 $[i, j]$左闭右开区间 $[i, j)$初始化$i 0,\ j n - 1$$i 0,\ j n$空区间条件$i j$$i j$循环条件while (i j)while (i j)目标在右侧i m 1i m 1目标在左侧j m - 1j m关键差异在于左闭右开中 $j$ 本身不参与比较因此当目标落在左半区时只需令j m把 $m$ 直接作为新的开区间右端而非m - 1而 $i$ 仍指向有效元素命中后向右收缩时必须i m 1。若将j m误写成j m - 1会漏掉nums[m-1]且破坏区间语义。原文档的建议是双闭区间的左右边界对称、缩小区间的操作也更直观一般情况下推荐使用双闭区间写法以降低出错概率。这一观点也解释了为何仓库中 binary_search_insertion、binary_search_edge 等进阶章节主要围绕双闭区间展开。亲手运行验证两种写法的输出仓库中每种语言的实现文件都自带驱动代码Driver Code可以直接运行验证。以 Python 为例参见 binary_search.py执行python codes/python/chapter_searching/binary_search.py输出为目标元素 6 的索引 2同样的验证可在 binary_search.java输出目标元素 6 的索引 2与 binary_search.go 中复现。驱动代码会依次调用双闭区间与左闭右开两个版本若两者对同一输入返回不同结果说明区间实现存在偏差——这也是自我测试两种写法的有效手段。日文版、英文版等语言分支下对应文件位于 ja/codes、en/codes。读者可尝试修改target的取值验证边界行为当target 0小于最小元素或target 40大于最大元素时返回 $-1$当target恰好落在数组两端时可用于检查循环边界是否漏判首尾元素。优点与局限什么场景该用它二分查找的优势时间效率高对数复杂度在大数据量下优势显著。文中给出的算例是 $n 2^{20}$ 时线性查找需 $1048576$ 次循环而二分查找仅需 $\log_2 2^{20} 20$ 次。空间占用小不需要像哈希查找那样开辟额外存储哈希表通常需维护装载因子与冲突链等额外空间属于原地搜索。二分查找的局限仅适用于有序数据若输入无序专门为二分查找先做排序并不划算——主流排序的时间复杂度为 $O(n \log n)$已高于线性查找的 $O(n)$而需要频繁插入元素的场景中为维持有序性而在数组中间插入的开销为 $O(n)$同样高昂。仅适用于数组二分查找依赖对中点元素 $m$ 的跳跃式随机访问链表访问第 $m$ 个节点需从头遍历因此基于链表实现的数据结构无法高效使用二分查找。小数据量下不如线性查找线性查找每轮仅 1 次比较二分查找每轮需要 1 次加法、1 次除法、13 次比较与 1 次加减合计 46 个基本操作。当 $n$ 较小时线性查找的实际速度反而更快。延伸与小结上述讨论假定数组元素互不重复。若元素存在重复二分查找找到一个等于target的索引就退化为更复杂的找最左 / 最右边界问题详见同章节的 binary_search_insertion.md 与 binary_search_edge.md若要理解为何有序 随机访问如此重要以及二分查找与其他搜索手段的整体取舍可阅读 searching_algorithm_revisited.md本文实现的完整图示、分步过程图与章节练习可继续查阅仓库 binary_search.assets 目录与 exercises.md。掌握二分查找的核心不在背诵代码而在于吃透区间不变量无论选择双闭还是左闭右开只要每次收缩都严格保持目标仍在新区间内、且新区间确实更小循环终止后返回的 $i$ 或 $-1$ 就必然正确。以此为基准去对照仓库中 15 种语言的实现便能在任何环境下写出风格统一、无越界错误的二分查找。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Hello 算法深度解析：二分查找的原理、双闭区间与左闭右开区间实现对比
Hello 算法深度解析二分查找的原理、双闭区间与左闭右开区间实现对比【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo二分查找binary search是《Hello 算法》搜索章节最基础的算法之一它建立在数据有序这一前提之上通过每轮将搜索区间减半的方式把查找的时间复杂度从线性降到对数级。本文以仓库中 日本语版二分查找文档与中文版 binary_search.md 同源为主体骨架结合 codes 下 Python、Java、Go、C 等多语言实现源码完整讲解双闭区间与左闭右开区间两种写法的异同、中点溢出问题的成因以及二分查找的适用边界。读完后你将能够徒手写出无 Bug 的二分查找并能针对不同区间定义准确推导循环条件与指针移动规则。问题定义在有序数组中定位目标文章开篇提出了一道经典面试题给定长度为 $n$ 的数组nums元素按从小到大排列且不重复若目标元素target存在于数组中则返回其索引否则返回 $-1$。以仓库中多个语言的测试用例为例如 binary_search.py 与 binary_search.java采用的统一示例为nums [1, 3, 6, 8, 12, 15, 23, 26, 31, 35] target 6 # 正确结果为索引 2对该问题的直观解法是线性扫描最坏情况下要比较 $n$ 次。而二分查找利用了有序 随机访问两个性质把每一轮的候选范围缩小一半因此得名 binary search。双闭区间写法算法主流程双闭区间 $[i, j]$ 表示左边界 $i$ 与右边界 $j$ 均被包含在搜索范围内。流程如下。初始化与循环结构初始化指针 $i 0$、$j n - 1$分别指向数组首元素与尾元素代表搜索区间 $[0, n-1]$。重复执行以下两步直到区间为空计算中点索引 $m \lfloor (i j) / 2 \rfloor$$\lfloor \rfloor$ 表示向下取整比较nums[m]与targetnums[m] target目标在右半区 $[m 1, j]$令 $i m 1$nums[m] target目标在左半区 $[i, m - 1]$令 $j m - 1$nums[m] target命中返回索引 $m$。若区间缩至为空仍未命中返回 $-1$。值得强调的是空区间的判定双闭区间下当 $i j$ 时区间才为空因此循环继续条件写作while (i j)。这是初学者最容易写错的地方——一旦把条件误写成i j就会漏掉 $i j$ 时边界元素仍可能等于target的情况。中点计算与整数溢出陷阱文中特别指出一个容易被忽略的细节$i$ 与 $j$ 都是int类型当数组极大时$i j$ 可能超出int的表示范围。为避免大数溢出通常改用等价形式$$m \lfloor i (j - i) / 2 \rfloor$$这一防溢出写法在仓库源码中得到了统一贯彻例如 binary_search.java 中的int m i (j - i) / 2;、binary_search.go 中的m : i (j-i)/2以及 binary_search.c 中的int m i (j - i) / 2;。而 binary_search.py 因为 Python 整数可无限增长仅受内存限制直接使用m (i j) // 2即可注释中也明确说明了这一语言差异。双闭区间参考实现以 Python 为例完整可运行代码见 binary_search.pydef binary_search(nums: list[int], target: int) - int: 二分查找双闭区间 # 初始化双闭区间 [0, n-1] 即 i, j 分别指向数组首元素、尾元素 i, j 0, len(nums) - 1 # 循环当搜索区间为空时跳出当 i j 时为空 while i j: m (i j) // 2 # 计算中点索引 m if nums[m] target: i m 1 # 此情况说明 target 在区间 [m1, j] 中 elif nums[m] target: j m - 1 # 此情况说明 target 在区间 [i, m-1] 中 else: return m # 找到目标元素返回其索引 return -1 # 未找到目标元素返回 -1各语言文件结构完全一致均同时包含两个区间版本的实现可直接对照学习语言文件路径Pythoncodes/python/chapter_searching/binary_search.pyJavacodes/java/chapter_searching/binary_search.javaGocodes/go/chapter_searching/binary_search.goCcodes/c/chapter_searching/binary_search.cCcodes/cpp/chapter_searching/binary_search.cppTypeScriptcodes/typescript/chapter_searching/binary_search.ts原文档中的 binary_search_step1.png 至 binary_search_step7.png 七张分步图完整演示了在示例数组上从区间 $[0, 9]$ 逐步收缩到命中索引 2 的全过程阅读时建议配合动画逐帧核对指针 $i$、$j$ 与中点 $m$ 的变化。复杂度分析时间复杂度 $O(\log n)$每轮循环区间减半最多执行 $\log_2 n$ 轮与数据规模呈对数关系。空间复杂度 $O(1)$算法仅使用 $i$、$j$、$m$ 三个指针无需任何与 $n$ 相关的额外空间。区间的另一种表示左闭右开除双闭区间外还有一种常见表示是左闭右开区间 $[i, j)$左端包含、右端不包含。此时区间 $[i, j)$ 在 $i j$ 时为空。两种写法在初始化、循环条件与收缩操作上存在三处系统性差异对比图见下以同仓库 binary_search.py 的左闭右开实现为例def binary_search_lcro(nums: list[int], target: int) - int: 二分查找左闭右开区间 # 初始化左闭右开区间 [0, n) 即 i, j 分别指向数组首元素、尾元素1 i, j 0, len(nums) # 循环当搜索区间为空时跳出当 i j 时为空 while i j: m (i j) // 2 # 计算中点索引 m if nums[m] target: i m 1 # 此情况说明 target 在区间 [m1, j) 中 elif nums[m] target: j m # 此情况说明 target 在区间 [i, m) 中 else: return m return -1两版差异可归纳为下表对比维度双闭区间 $[i, j]$左闭右开区间 $[i, j)$初始化$i 0,\ j n - 1$$i 0,\ j n$空区间条件$i j$$i j$循环条件while (i j)while (i j)目标在右侧i m 1i m 1目标在左侧j m - 1j m关键差异在于左闭右开中 $j$ 本身不参与比较因此当目标落在左半区时只需令j m把 $m$ 直接作为新的开区间右端而非m - 1而 $i$ 仍指向有效元素命中后向右收缩时必须i m 1。若将j m误写成j m - 1会漏掉nums[m-1]且破坏区间语义。原文档的建议是双闭区间的左右边界对称、缩小区间的操作也更直观一般情况下推荐使用双闭区间写法以降低出错概率。这一观点也解释了为何仓库中 binary_search_insertion、binary_search_edge 等进阶章节主要围绕双闭区间展开。亲手运行验证两种写法的输出仓库中每种语言的实现文件都自带驱动代码Driver Code可以直接运行验证。以 Python 为例参见 binary_search.py执行python codes/python/chapter_searching/binary_search.py输出为目标元素 6 的索引 2同样的验证可在 binary_search.java输出目标元素 6 的索引 2与 binary_search.go 中复现。驱动代码会依次调用双闭区间与左闭右开两个版本若两者对同一输入返回不同结果说明区间实现存在偏差——这也是自我测试两种写法的有效手段。日文版、英文版等语言分支下对应文件位于 ja/codes、en/codes。读者可尝试修改target的取值验证边界行为当target 0小于最小元素或target 40大于最大元素时返回 $-1$当target恰好落在数组两端时可用于检查循环边界是否漏判首尾元素。优点与局限什么场景该用它二分查找的优势时间效率高对数复杂度在大数据量下优势显著。文中给出的算例是 $n 2^{20}$ 时线性查找需 $1048576$ 次循环而二分查找仅需 $\log_2 2^{20} 20$ 次。空间占用小不需要像哈希查找那样开辟额外存储哈希表通常需维护装载因子与冲突链等额外空间属于原地搜索。二分查找的局限仅适用于有序数据若输入无序专门为二分查找先做排序并不划算——主流排序的时间复杂度为 $O(n \log n)$已高于线性查找的 $O(n)$而需要频繁插入元素的场景中为维持有序性而在数组中间插入的开销为 $O(n)$同样高昂。仅适用于数组二分查找依赖对中点元素 $m$ 的跳跃式随机访问链表访问第 $m$ 个节点需从头遍历因此基于链表实现的数据结构无法高效使用二分查找。小数据量下不如线性查找线性查找每轮仅 1 次比较二分查找每轮需要 1 次加法、1 次除法、13 次比较与 1 次加减合计 46 个基本操作。当 $n$ 较小时线性查找的实际速度反而更快。延伸与小结上述讨论假定数组元素互不重复。若元素存在重复二分查找找到一个等于target的索引就退化为更复杂的找最左 / 最右边界问题详见同章节的 binary_search_insertion.md 与 binary_search_edge.md若要理解为何有序 随机访问如此重要以及二分查找与其他搜索手段的整体取舍可阅读 searching_algorithm_revisited.md本文实现的完整图示、分步过程图与章节练习可继续查阅仓库 binary_search.assets 目录与 exercises.md。掌握二分查找的核心不在背诵代码而在于吃透区间不变量无论选择双闭还是左闭右开只要每次收缩都严格保持目标仍在新区间内、且新区间确实更小循环终止后返回的 $i$ 或 $-1$ 就必然正确。以此为基准去对照仓库中 15 种语言的实现便能在任何环境下写出风格统一、无越界错误的二分查找。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
