《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 为主线结合仓库中 Python、C、Java、Go、C 等多语言实现见 ru/codes 下的chapter_searching/binary_search.*完整讲解二分查找的算法流程、两种区间表示法双闭区间与左闭右开区间的编码差异、整数溢出陷阱以及它的复杂度与适用边界。读完本文你将能独立手写两种区间版本的二分查找并准确判断它在何种场景下适用、何种场景下应当放弃。问题定义与算法思想给定一个长度为 $n$ 的数组nums元素按升序排列且不重复。请查找并返回元素target在数组中的索引若数组不包含该元素则返回 $-1$。二分查找之所以高效核心在于每轮淘汰一半数据它先比较中间元素与target的大小关系由于数组有序一次比较即可确定目标位于中间元素的左侧还是右侧从而把搜索区间缩小一半。重复这一过程搜索区间以指数速度收敛。算法流程双闭区间版本首先初始化两个指针 $i 0$ 和 $j n - 1$分别指向数组的首尾元素从而划定搜索区间 $[0, n-1]$。注意方括号表示闭区间即区间包含边界值本身。接下来在循环中反复执行以下两步计算中点索引$m \lfloor (i j) / 2 \rfloor$其中 $\lfloor : \rfloor$ 表示向下取整运算。比较nums[m]与target出现三种情况若nums[m] target说明target位于区间 $[m1, j]$令 $i m 1$若nums[m] target说明target位于区间 $[i, m-1]$令 $j m - 1$若nums[m] target说明找到目标元素直接返回索引 $m$。若数组不包含目标元素搜索区间最终会收缩为空区间此时返回 $-1$。完整的分步推进过程可参见文档中的binary_search_step1.png至binary_search_step7.png七张示意ru/docs/chapter_searching/binary_search.assets。以文档与源码中共同使用的测试数据为例nums [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]target 6。首轮 $i0, j9, m4$nums[4]12 6令 $j3$第二轮 $i0, j3, m1$nums[1]3 6令 $i2$第三轮 $i2, j3, m2$nums[2]6命中并返回索引 $2$。整数溢出陷阱与安全的中点公式值得特别注意的是由于 $i$ 和 $j$ 均为int类型$i j$ 之和可能超出int的表示范围。为避免溢出实际编码中通常使用公式 $m \lfloor i (j - i) / 2 \rfloor$ 来计算中点。这一点在仓库源码中得到了严格贯彻在 binary_search.cpp、binary_search.java、binary_search.go 和 binary_search.c 中中点计算统一写作i (j - i) / 2。唯一的例外是 Python 实现 binary_search.py由于 Python 整数可以任意大仅受内存限制源码直接采用(i j) // 2并在注释中明确说明无需考虑大数溢出——这正是不同语言特性在算法实现上的典型体现。完整实现代码仓库中每个语言文件都同时包含双闭区间与左闭右开区间两个版本。以 Python 为例binary_search.pydef binary_search(nums: list[int], target: int) - int: 二分查找双闭区间 i, j 0, len(nums) - 1 while i j: m (i j) // 2 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 # 未找到目标元素返回 -1C 版本binary_search.cpp结构一致区别仅在于使用i (j - i) / 2规避溢出C 版本binary_search.c因无内建动态数组函数签名额外携带长度参数len。各语言文件的 Driver 代码均以target 6对nums [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]进行验证预期输出索引2可直接运行核对。复杂度分析时间复杂度 $O(\log n)$二分查找循环中区间每轮缩小一半因此迭代次数为 $\log_2 n$。空间复杂度 $O(1)$指针 $i$ 和 $j$ 仅占用常数级别的内存。与线性搜索对比对数复杂度在大数据量下优势显著当 $n 2^{20}$ 时线性搜索最坏需要 $2^{20} 1048576$ 次迭代而二分查找仅需 $\log_2 2^{20} 20$ 次迭代差距接近五个数量级。两种区间表示法双闭区间与左闭右开区间除双闭区间 $[0, n-1]$ 外业界常用的另一种表示是左闭右开区间$[0, n)$即左边界包含、右边界不包含。在该表示下当 $i j$ 时区间 $[i, j)$ 为空。基于此表示可实现功能完全相同的二分查找见 binary_search.pydef binary_search_lcro(nums: list[int], target: int) - int: 二分查找左闭右开区间 i, j 0, len(nums) while i j: m (i j) // 2 if nums[m] target: i m 1 # target 在区间 [m1, j) elif nums[m] target: j m # target 在区间 [i, m) else: return m return -1两种区间表示在算法上的差异集中在三处初始化、循环条件、区间收缩操作具体对比如下对比项双闭区间 $[0, n-1]$左闭右开区间 $[0, n)$初始化i 0, j n - 1i 0, j n循环条件while (i j)while (i j)区间空判定$i j$ 时为空$i j$ 时为空nums[m] target时i m 1区间 $[m1, j]$i m 1区间 $[m1, j)$nums[m] target时j m - 1区间 $[i, m-1]$j m区间 $[i, m)$两种写法均可正确运行。但由于双闭区间的两个边界均为闭区间指针 $i$、$j$ 的收缩操作呈现出对称性i m 1与j m - 1边界条件更不容易出错因此文档明确建议优先采用双闭区间写法。左闭右开区间在后续章节如 binary_search_edge.md 中的查找边界问题中另有用途理解两者的映射关系有助于举一反三。优势与局限何时该用、何时该弃二分查找在时间与空间两个维度都表现优异时间效率高对数时间复杂度在大规模数据上优势明显上文 $n 2^{20}$ 的例子即为佐证不占用额外内存相比依赖外部存储的搜索方案例如哈希查找二分查找在内存占用上显著更省。但二分查找并非万能主要受限于以下三点仅适用于有序数据。若输入数据无序为了二分查找而专门排序并不划算——排序算法的时间复杂度通常为 $O(n \log n)$高于线性搜索与二分查找本身。若元素需要频繁插入为了维持数组有序必须将元素放到特定位置这需要 $O(n)$ 时间代价同样高昂。仅适用于数组顺序存储结构。二分查找依赖跳跃式访问元素而链表中的随机访问效率很低因此二分查找不适用于链表及其衍生结构。数据量较小时线性搜索反而更优。线性搜索每步只需 1 次比较而二分查找每步需要 1 次加法、1 次除法、13 次比较以及额外的加减运算共约 46 次基本操作。当 $n$ 较小时线性搜索可能更快。延伸阅读二分查找的思想还可以扩展到更多变体在有序数组中查找插入点binary_search_insertion.md、查找目标元素的左/右边界binary_search_edge.md、用哈希表替代线性查找replace_linear_by_hashing.md以及搜索策略的横向对比searching_algorithm_revisited.md。另外递归形式的二分查找实现见 binary_search_recur分治章节。建议读者在掌握本文两种区间写法后进一步阅读上述章节理解二分查找如何从查找元素演化为解决边界类问题。【免费下载链接】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 为主线结合仓库中 Python、C、Java、Go、C 等多语言实现见 ru/codes 下的chapter_searching/binary_search.*完整讲解二分查找的算法流程、两种区间表示法双闭区间与左闭右开区间的编码差异、整数溢出陷阱以及它的复杂度与适用边界。读完本文你将能独立手写两种区间版本的二分查找并准确判断它在何种场景下适用、何种场景下应当放弃。问题定义与算法思想给定一个长度为 $n$ 的数组nums元素按升序排列且不重复。请查找并返回元素target在数组中的索引若数组不包含该元素则返回 $-1$。二分查找之所以高效核心在于每轮淘汰一半数据它先比较中间元素与target的大小关系由于数组有序一次比较即可确定目标位于中间元素的左侧还是右侧从而把搜索区间缩小一半。重复这一过程搜索区间以指数速度收敛。算法流程双闭区间版本首先初始化两个指针 $i 0$ 和 $j n - 1$分别指向数组的首尾元素从而划定搜索区间 $[0, n-1]$。注意方括号表示闭区间即区间包含边界值本身。接下来在循环中反复执行以下两步计算中点索引$m \lfloor (i j) / 2 \rfloor$其中 $\lfloor : \rfloor$ 表示向下取整运算。比较nums[m]与target出现三种情况若nums[m] target说明target位于区间 $[m1, j]$令 $i m 1$若nums[m] target说明target位于区间 $[i, m-1]$令 $j m - 1$若nums[m] target说明找到目标元素直接返回索引 $m$。若数组不包含目标元素搜索区间最终会收缩为空区间此时返回 $-1$。完整的分步推进过程可参见文档中的binary_search_step1.png至binary_search_step7.png七张示意ru/docs/chapter_searching/binary_search.assets。以文档与源码中共同使用的测试数据为例nums [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]target 6。首轮 $i0, j9, m4$nums[4]12 6令 $j3$第二轮 $i0, j3, m1$nums[1]3 6令 $i2$第三轮 $i2, j3, m2$nums[2]6命中并返回索引 $2$。整数溢出陷阱与安全的中点公式值得特别注意的是由于 $i$ 和 $j$ 均为int类型$i j$ 之和可能超出int的表示范围。为避免溢出实际编码中通常使用公式 $m \lfloor i (j - i) / 2 \rfloor$ 来计算中点。这一点在仓库源码中得到了严格贯彻在 binary_search.cpp、binary_search.java、binary_search.go 和 binary_search.c 中中点计算统一写作i (j - i) / 2。唯一的例外是 Python 实现 binary_search.py由于 Python 整数可以任意大仅受内存限制源码直接采用(i j) // 2并在注释中明确说明无需考虑大数溢出——这正是不同语言特性在算法实现上的典型体现。完整实现代码仓库中每个语言文件都同时包含双闭区间与左闭右开区间两个版本。以 Python 为例binary_search.pydef binary_search(nums: list[int], target: int) - int: 二分查找双闭区间 i, j 0, len(nums) - 1 while i j: m (i j) // 2 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 # 未找到目标元素返回 -1C 版本binary_search.cpp结构一致区别仅在于使用i (j - i) / 2规避溢出C 版本binary_search.c因无内建动态数组函数签名额外携带长度参数len。各语言文件的 Driver 代码均以target 6对nums [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]进行验证预期输出索引2可直接运行核对。复杂度分析时间复杂度 $O(\log n)$二分查找循环中区间每轮缩小一半因此迭代次数为 $\log_2 n$。空间复杂度 $O(1)$指针 $i$ 和 $j$ 仅占用常数级别的内存。与线性搜索对比对数复杂度在大数据量下优势显著当 $n 2^{20}$ 时线性搜索最坏需要 $2^{20} 1048576$ 次迭代而二分查找仅需 $\log_2 2^{20} 20$ 次迭代差距接近五个数量级。两种区间表示法双闭区间与左闭右开区间除双闭区间 $[0, n-1]$ 外业界常用的另一种表示是左闭右开区间$[0, n)$即左边界包含、右边界不包含。在该表示下当 $i j$ 时区间 $[i, j)$ 为空。基于此表示可实现功能完全相同的二分查找见 binary_search.pydef binary_search_lcro(nums: list[int], target: int) - int: 二分查找左闭右开区间 i, j 0, len(nums) while i j: m (i j) // 2 if nums[m] target: i m 1 # target 在区间 [m1, j) elif nums[m] target: j m # target 在区间 [i, m) else: return m return -1两种区间表示在算法上的差异集中在三处初始化、循环条件、区间收缩操作具体对比如下对比项双闭区间 $[0, n-1]$左闭右开区间 $[0, n)$初始化i 0, j n - 1i 0, j n循环条件while (i j)while (i j)区间空判定$i j$ 时为空$i j$ 时为空nums[m] target时i m 1区间 $[m1, j]$i m 1区间 $[m1, j)$nums[m] target时j m - 1区间 $[i, m-1]$j m区间 $[i, m)$两种写法均可正确运行。但由于双闭区间的两个边界均为闭区间指针 $i$、$j$ 的收缩操作呈现出对称性i m 1与j m - 1边界条件更不容易出错因此文档明确建议优先采用双闭区间写法。左闭右开区间在后续章节如 binary_search_edge.md 中的查找边界问题中另有用途理解两者的映射关系有助于举一反三。优势与局限何时该用、何时该弃二分查找在时间与空间两个维度都表现优异时间效率高对数时间复杂度在大规模数据上优势明显上文 $n 2^{20}$ 的例子即为佐证不占用额外内存相比依赖外部存储的搜索方案例如哈希查找二分查找在内存占用上显著更省。但二分查找并非万能主要受限于以下三点仅适用于有序数据。若输入数据无序为了二分查找而专门排序并不划算——排序算法的时间复杂度通常为 $O(n \log n)$高于线性搜索与二分查找本身。若元素需要频繁插入为了维持数组有序必须将元素放到特定位置这需要 $O(n)$ 时间代价同样高昂。仅适用于数组顺序存储结构。二分查找依赖跳跃式访问元素而链表中的随机访问效率很低因此二分查找不适用于链表及其衍生结构。数据量较小时线性搜索反而更优。线性搜索每步只需 1 次比较而二分查找每步需要 1 次加法、1 次除法、13 次比较以及额外的加减运算共约 46 次基本操作。当 $n$ 较小时线性搜索可能更快。延伸阅读二分查找的思想还可以扩展到更多变体在有序数组中查找插入点binary_search_insertion.md、查找目标元素的左/右边界binary_search_edge.md、用哈希表替代线性查找replace_linear_by_hashing.md以及搜索策略的横向对比searching_algorithm_revisited.md。另外递归形式的二分查找实现见 binary_search_recur分治章节。建议读者在掌握本文两种区间写法后进一步阅读上述章节理解二分查找如何从查找元素演化为解决边界类问题。【免费下载链接】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），仅供参考