1. 项目概述为什么二分查找值得你花时间如果你刷过算法题或者在工作中处理过有序数据大概率听过“二分查找”这个名字。它听起来简单但真正能把它写对、写稳、写快的人远没有想象中多。我见过太多人包括我自己早期在边界条件上栽跟头不是死循环就是漏掉元素一个简单的while (left right)和while (left right)就能把人绕晕。今天我们不谈那些高深莫测的理论就从一个一线开发者的视角彻底拆解二分查找并给你一个经过大量实战检验、几乎能覆盖所有场景的“万能模板”。这个模板不是魔法而是对二分查找本质理解的结晶它能帮你把思考重心从“边界怎么写”转移到“问题本身怎么解”上。简单说二分查找是一种在有序集合中快速定位目标值的算法。它的核心思想是“分而治之”每次比较中间元素根据比较结果将搜索范围缩小一半。时间复杂度是O(log n)这意味着对于一个有10亿个元素的有序数组你最多只需要比较30次左右就能找到答案效率极高。无论是面试中的高频考点还是实际开发中处理日志时间戳、用户ID范围、配置表查询等场景二分查找都是你必须熟练掌握的基本功。本文适合所有正在学习算法、准备技术面试或希望优化代码中查找逻辑的开发者。我们将从最基础的原理讲起一步步推导出那个“万能模板”并通过多个变种问题让你真正掌握其精髓。2. 二分查找的核心思想与“坑点”全解析2.1 算法本质不只是“找数字”很多人对二分查找的理解停留在“在一个有序数组里找一个数”。这没错但太片面了。二分查找更本质的是一种基于“有序性”和“单调性”进行快速决策的框架。这里的“有序”不一定是数字大小可以是任何满足单调关系的属性比如时间先后、版本号大小、任务优先级等。算法利用这种单调性通过一次比较就能果断地抛弃一半不可能存在答案的搜索空间。举个例子想象你在翻一本厚厚的字典找单词。你不会从第一页开始一页页翻而是先打开中间一页看看上面的单词。如果你要找的单词按字母序在这页单词之后那么前半本书就可以完全不用看了反之亦然。你不断重复这个过程每次都能扔掉一半的页数。这就是二分查找最直观的体现。2.2 那些年我们踩过的“边界”之坑二分查找的代码框架看似简单但细节是魔鬼。几乎所有错误都集中在循环条件和边界更新上。下面我罗列几个最常见的“坑”你看看自己中过几个循环条件不清晰到底用while (left right)还是while (left right)这是第一个分水岭。前者对应的搜索区间是闭区间[left, right]后者是左闭右开区间[left, right)。选择不同后续的边界更新和返回值处理就完全不同。中间值计算溢出计算中间索引时很多人会写mid (left right) / 2。这在left和right都是很大的整数时left right可能会超出整型范围导致溢出。正确的写法是mid left (right - left) / 2。边界更新死循环在while (left right)的框架下如果你在目标值大于中间值时执行left mid而在某些情况下mid的计算结果始终等于left那么left就永远不会更新导致死循环。例如left 3, right 4时mid 3如果条件分支让left mid则left还是3陷入无限循环。返回值意义混淆循环结束后left和right指向哪里是目标值的位置还是第一个大于目标值的位置或者是插入位置如果不清楚循环不变量的意义根本无法确定返回哪个变量。这些坑的根源在于没有明确定义搜索区间和循环不变量。接下来我们就从这两个核心概念出发构建一个牢固的思维框架。3. 构建思维基石搜索区间与循环不变量3.1 明确你的“搜索空间”两种区间定义在动笔写代码之前你必须先想清楚你定义的left和right初始值代表的是一个什么样的区间这个区间在整个循环过程中需要始终保持一个不变的性质循环不变量。第一种闭区间[left, right]定义left和right都指向有效的、可能包含答案的索引。初始化left 0,right nums.length - 1。循环条件while (left right)。因为当left right时区间[left, right]仍然包含一个元素有必要进行最后一次检查。边界更新如果nums[mid] target说明目标值只可能在右边且mid本身已经检查过不是目标所以新的左边界是mid 1。如果nums[mid] target说明目标值只可能在左边且mid本身已经检查过不是目标所以新的右边界是mid - 1。循环结束当left right时搜索区间为空说明目标不存在。第二种左闭右开区间[left, right)定义left指向可能包含答案的索引right指向的是不包含在搜索空间内的第一个索引类似于迭代器的end()。初始化left 0,right nums.length。注意right初始值等于数组长度因为它指向的是“尾后”位置。循环条件while (left right)。当left right时区间[left, right)已经为空没有元素需要检查。边界更新如果nums[mid] target目标在右边mid已检查非目标新左边界left mid 1。如果nums[mid] target目标在左边但注意right是开区间它指向的是不包含的位置。mid已经比目标大所以新的右边界应该把mid排除在外即right mid。循环结束当left right时搜索区间为空。实操心得我强烈建议初学者甚至是有经验的开发者在解决新问题时优先使用左闭右开区间[left, right)。原因有三第一它的边界更新逻辑更统一left mid 1和right mid不容易出错第二它处理“寻找边界”类问题如第一个大于等于target的位置时更加自然第三它的结束条件left right直接指向一个非常有意义的位置通常是插入位置或边界便于后续处理。在后续的“万能模板”中我们也将基于此区间定义。3.2 循环不变量你的算法“信仰”循环不变量是指在循环开始前、每次迭代后都保持不变的条件。对于二分查找我们的循环不变量就是目标值如果存在一定在当前定义的搜索区间内。在[left, right)区间定义下这个不变量就是在每一轮循环开始时目标值target如果存在于数组中那么它的索引i一定满足left i right。我们所有的边界更新操作都必须维护这个不变量。当nums[mid] target时我们知道target不可能在[left, mid]区间因为数组有序所以将left更新为mid 1新的区间[mid1, right)依然包含target如果存在。当nums[mid] target时注意这里用了这是寻找左边界的关键我们知道target可能在[left, mid]区间但mid本身可能是目标也可能是第一个大于目标的值。为了保持区间左闭右开我们将right更新为mid新区间[left, mid)依然可能包含target如果target存在且mid是第一个等于target的位置那么target的实际索引就是mid但我们的区间是[left, mid)不包含mid这会不会矛盾不这恰恰是我们寻找“左边界”的意图我们让区间不断向左收缩直到锁定边界。最终left会指向那个边界。想明白了搜索区间和循环不变量代码怎么写就变成了一个按部就班的填空题。下面我们就来揭晓那个“万能模板”。4. 二分查找万能模板解析与实现这个模板的核心是处理三种最常见的二分查找场景1查找精确值2查找左边界第一个大于等于target的值3查找右边界最后一个小于等于target的值。我们将用一个统一的框架来应对。4.1 模板代码与注释/** * 二分查找万能模板 * param nums 有序数组假设为非递减 * param target 目标值 * return 根据场景不同返回索引值。未找到时返回-1或插入位置。 */ public int binarySearch(int[] nums, int target) { // 防御性编程 if (nums null || nums.length 0) { return -1; // 或根据场景返回0 } int left 0; int right nums.length; // 注意使用左闭右开区间 [left, right) // 循环不变量目标值若存在其索引i一定满足 left i right while (left right) { // 防止溢出 int mid left (right - left) / 2; // ********** 核心决策逻辑 ********** // // 场景1查找精确值 (标准二分查找) // if (nums[mid] target) { // return mid; // } else if (nums[mid] target) { // left mid 1; // } else { // right mid; // } // 场景2查找左边界 (第一个 target 的元素) if (nums[mid] target) { right mid; // 目标在左半部分包括mid本身因为mid可能就是要找的左边界 } else { left mid 1; // 目标在右半部分 } // 场景3查找右边界 (最后一个 target 的元素) // 通常转化为“查找第一个 target 的元素”然后将其索引减1 // if (nums[mid] target) { // left mid 1; // 目标在右半部分包括mid // } else { // right mid; // } // 循环结束后left是第一个target的位置left-1就是最后一个target的位置 } // 循环结束left right // 对于查找左边界场景2 // left 指向第一个 target 的位置。 // 需要检查 left 是否越界以及 nums[left] 是否等于 target。 if (left nums.length || nums[left] ! target) { return -1; // 未找到目标值 } return left; // 对于查找精确值场景1在循环内已返回。 // 对于查找右边界场景3返回 left - 1并同样需要检查有效性。 }4.2 模板逐行解读与设计逻辑初始化 (right nums.length)我们坚持使用左闭右开区间[left, right)。right初始化为数组长度意味着整个数组都在初始搜索空间内。循环条件 (while (left right))只要区间不为空left right就继续搜索。当left right时区间变为[left, left)这是一个空区间循环结束。中间值计算 (mid left (right - left) / 2)这是防止整数溢出的标准写法。在Java、C等语言中(left right) / 2在两者之和超过Integer.MAX_VALUE时会溢出变成负数导致计算错误。left (right - left) / 2在数学上等价但避免了加法溢出。核心决策逻辑这是模板的灵魂需要根据具体场景调整if判断条件。查找左边界 (第一个 target)使用if (nums[mid] target)。为什么是因为我们的目标是找到第一个大于或等于target的位置。当nums[mid]等于target时它可能就是我们要找的左边界但我们不能直接返回因为左边可能还有更早的等于target的元素。所以我们将right设为mid在左侧区间[left, mid)中继续寻找。这个操作保证了right的左边包括right指向的位置始终满足 target。最终当区间收缩到一点时left就指向了第一个满足 target的位置。查找精确值在循环内判断相等并返回。这是最基础的变体。查找右边界模板中注释了另一种逻辑。通常寻找最后一个 target的元素可以转化为寻找第一个 target的元素然后将其索引减1。代码中当nums[mid] target时说明目标在右边包括mid所以left mid 1。循环结束后left指向第一个 target的位置那么left - 1就是最后一个 target的位置。边界更新这是维护循环不变量的关键步骤。当条件满足如nums[mid] target我们将right更新为mid。因为mid可能已经是或超过了目标边界新的搜索区间[left, mid)仍然可能包含我们要找的边界。当条件不满足如nums[mid] target我们将left更新为mid 1。因为mid已经明确小于目标它绝不可能是我们要找的位置所以从mid1开始搜索。后处理循环结束后left和right相等。这个位置的意义取决于你的决策逻辑。对于查找左边界left是第一个 target的索引。你需要检查①left是否等于数组长度意味着所有元素都小于target②nums[left]是否等于target如果只想找等于target的左边界。根据检查结果返回left或-1。对于查找右边界left是第一个 target的索引那么left - 1就是最后一个 target的索引。同样需要检查left - 1是否越界left 0以及值是否匹配。注意事项这个模板的美妙之处在于你只需要修改核心决策逻辑中的比较条件nums[mid]和target的关系以及最后的返回值处理就能适应绝大多数二分查找问题。再也不用为left、right怎么变而头疼了。5. 实战演练用模板解决三类经典问题理论说得再多不如代码跑一遍。我们直接用上面的模板来解决LeetCode上最经典的三个二分查找问题。我会展示如何将模板“套用”进去并解释每一步的思考过程。5.1 案例一基础查找LeetCode 704题目给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果目标值存在返回下标否则返回-1。分析这是最标准的二分查找查找精确值。我们可以在循环内部判断相等并直接返回。模板应用class Solution { public int search(int[] nums, int target) { if (nums null || nums.length 0) return -1; int left 0, right nums.length; // [left, right) while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; // 找到直接返回 } else if (nums[mid] target) { left mid 1; // 目标在右侧 } else { right mid; // 目标在左侧 } } // 循环结束未找到 return -1; } }要点在找到精确匹配时立即返回这是与寻找边界问题的主要区别。循环内的else分支对应nums[mid] target此时更新right mid。5.2 案例二寻找左边界LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 - 找起始位置题目找出给定目标值在数组中的开始位置。如果不存在返回-1。分析这等价于寻找第一个 target的元素位置并且需要验证该位置的值是否等于target。模板应用class Solution { public int[] searchRange(int[] nums, int target) { int start findLeftBound(nums, target); if (start -1) return new int[]{-1, -1}; int end findRightBound(nums, target); return new int[]{start, end}; } private int findLeftBound(int[] nums, int target) { if (nums null || nums.length 0) return -1; int left 0, right nums.length; // [left, right) while (left right) { int mid left (right - left) / 2; // 核心寻找第一个 target 的位置 if (nums[mid] target) { right mid; } else { left mid 1; } } // 循环结束left是第一个target的位置 // 检查1.是否越界 2.值是否等于target if (left nums.length || nums[left] ! target) { return -1; } return left; } private int findRightBound(int[] nums, int target) { if (nums null || nums.length 0) return -1; int left 0, right nums.length; // [left, right) while (left right) { int mid left (right - left) / 2; // 核心寻找第一个 target 的位置 if (nums[mid] target) { right mid; } else { left mid 1; } } // 循环结束left是第一个target的位置 // 那么 left - 1 就是最后一个 target 的位置 // 检查1. left-1是否越界 2. 值是否等于target if (left - 1 0 || nums[left - 1] ! target) { return -1; } return left - 1; } }要点findLeftBound函数完全使用了模板中的“场景2”逻辑。后处理时left可能是数组长度所有数都小于target也可能指向一个不等于target的数需要检查。findRightBound函数使用了“寻找第一个大于target的位置”的策略。注意if条件变成了nums[mid] target。循环结束后left - 1就是我们要的右边界。同样需要检查有效性。5.3 案例三寻找峰值元素LeetCode 162题目峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组nums找到峰值元素并返回其索引。数组可能包含多个峰值返回任何一个即可。你可以假设nums[-1] nums[n] -∞。分析数组无序但根据题意和边界条件我们可以利用局部单调性进行二分。核心是比较nums[mid]和nums[mid1]如果nums[mid] nums[mid1]说明处于上升坡峰值一定在mid右侧包括mid1所以left mid 1。如果nums[mid] nums[mid1]说明mid本身可能是一个峰值或者处于下降坡峰值在mid左侧包括mid所以right mid。 这依然符合我们“缩小搜索区间”的二分思想。模板应用class Solution { public int findPeakElement(int[] nums) { if (nums null || nums.length 0) return -1; int left 0, right nums.length - 1; // 注意这里用闭区间更方便处理mid1 while (left right) { // 循环直到 left right int mid left (right - left) / 2; if (nums[mid] nums[mid 1]) { // 上坡峰值在右侧 left mid 1; } else { // 下坡或峰顶峰值在左侧包含mid right mid; } } // 当 left right 时即为我们找到的一个峰值索引 return left; } }要点这个问题展示了二分查找不局限于“有序数组”只要存在某种单调性这里是局部单调性沿着某个方向走一定能找到峰值就可以使用二分来快速逼近答案。我们调整了比较对象nums[mid]和nums[mid1]但边界更新的逻辑内核与模板一致。6. 避坑指南与高频问题排查即使有了模板在实际编码和调试中还是会遇到一些典型问题。下面是我总结的“踩坑实录”和解决方案。6.1 问题一死循环现象程序在某个测试用例上永远运行不结束。根因边界更新不当导致搜索区间无法继续缩小。最常见于while (left right)且更新语句为left mid的情况。案例在[left, right)区间left 0, right 1计算mid 0。如果分支判断让left mid则left仍为0区间不变陷入死循环。解决牢记模板的更新规则在[left, right)下left的更新一定是mid 1right的更新一定是mid。这能保证区间每次迭代至少缩小1。6.2 问题二返回结果错误或漏掉元素现象对于某些边界情况如目标值在数组开头、结尾或不存在时返回的索引错误。根因后处理逻辑不完整或循环条件选择错误。排查清单检查初始区间确认right的初始化是nums.length左闭右开还是nums.length - 1闭区间必须与循环条件匹配。检查循环结束后的状态画出区间收缩的最终状态。对于左边界查找循环结束后left指向第一个 target的位置。你需要思考如果所有元素都小于targetleft会等于nums.length。你的代码处理了吗如果left在数组范围内但nums[left] ! target说明target不存在。你的代码返回-1了吗单步调试用最少的元素如空数组、单元素数组、两个元素数组和边界值目标值小于最小值、等于某个值、大于最大值作为测试用例在脑中或纸上模拟代码运行。6.3 问题三如何选择while (left right)还是while (left right)这是一个哲学问题但模板给出了明确答案统一使用while (left right)和左闭右开区间[left, right)。一致性所有二分问题找精确值、找左边界、找右边界都可以用这套框架解决只需修改核心判断条件和后处理。简洁性循环结束条件left right指向的位置通常就是答案或答案的相邻位置语义清晰。减少错误避免了在while (left right)循环结束后还需要纠结left和right哪个是答案的麻烦。当然如果你对闭区间[left, right]非常熟悉并且能保证不出错继续使用也可以。但从教学和统一心智模型的角度我强烈推荐左闭右开区间。6.4 一份自检清单在写完二分查找代码后问自己以下几个问题数组为空或为null时我的代码能处理吗目标值比所有元素都小或都大时返回值正确吗目标值不存在但数组中有其他值时返回值是-1吗数组中有重复的目标值时我是在找第一个还是最后一个还是任意一个我的mid计算方式防止溢出吗我的循环在left和right相邻时能正常退出吗把这几个问题过一遍能帮你排除90%的二分查找Bug。7. 模板的变通与高阶应用场景万能模板不是死板的教条理解其原理后你可以灵活变通解决更复杂的问题。7.1 在非整数域上的二分二分答案二分查找的思想可以应用于任何具有单调性的函数寻找满足某个条件的边界值。典型问题是“二分答案”。例如LeetCode 410 “分割数组的最大值”LeetCode 875 “爱吃香蕉的珂珂”。核心思路确定搜索范围[left, right]这个范围是答案可能的最小值和最大值。定义一个判定函数check(mid)判断当答案是mid时是否满足题目要求。这个函数需要基于题目逻辑实现并且具有单调性如果mid满足那么所有大于或小于mid的值也可能满足。在while (left right)循环中计算mid根据check(mid)的结果按照模板更新left或right。循环结束后的left或right就是所求的答案。示例框架// 假设我们要找满足条件的最小值 int left minPossibleAnswer; // 答案下界 int right maxPossibleAnswer; // 答案上界 while (left right) { int mid left (right - left) / 2; if (check(mid)) { // mid 满足条件说明答案可能 mid向左搜索包含mid right mid; } else { // mid 不满足条件说明答案必须 mid向右搜索 left mid 1; } } // 循环结束left 是满足条件的最小值 return left;7.2 在复杂数据结构上的应用二分查找的关键是“随机访问”中间元素。因此只要数据结构支持O(1)时间的索引访问就可以应用。例如数组最直接的应用。内存中的连续数据结构如ArrayList。通过索引映射的虚拟数组例如在一个已知最大值和单调性的数学函数上寻找解。对于链表等不支持随机访问的数据结构二分查找的O(log n)优势就不复存在了因为访问中间节点需要O(n)时间。7.3 与其它算法结合二分查找常作为子过程嵌入更复杂的算法中快速选择算法在快速排序的 partition 过程中通过比较 pivot 的索引与目标索引决定对哪边进行递归类似于二分。二叉搜索树BST的查找过程本身就是二分思想在树形结构上的体现。数据库索引B树索引的层间查找本质上也是多路二分。掌握二分查找的模板不仅仅是学会了一个算法更是掌握了一种高效缩小问题规模的思维方式。这种思维是优化算法、降低时间复杂度的利器。我个人的体会是初期死记硬背这个模板在各类题目中反复套用、调试、理解。当熟练到一定程度后你就不再需要“背”了因为你对搜索区间和循环不变量的理解已经深入骨髓可以针对任何变种问题迅速推导出正确的代码。这大概就是所谓“无招胜有招”的境界吧。最后一个小技巧在面试中如果你被问到二分查找可以先和面试官明确你使用的区间定义“我习惯使用左闭右开区间”然后基于此展开书写和解释这会让你的思路显得非常清晰和专业。
1. 项目概述为什么二分查找值得你花时间如果你刷过算法题或者在工作中处理过有序数据大概率听过“二分查找”这个名字。它听起来简单但真正能把它写对、写稳、写快的人远没有想象中多。我见过太多人包括我自己早期在边界条件上栽跟头不是死循环就是漏掉元素一个简单的while (left right)和while (left right)就能把人绕晕。今天我们不谈那些高深莫测的理论就从一个一线开发者的视角彻底拆解二分查找并给你一个经过大量实战检验、几乎能覆盖所有场景的“万能模板”。这个模板不是魔法而是对二分查找本质理解的结晶它能帮你把思考重心从“边界怎么写”转移到“问题本身怎么解”上。简单说二分查找是一种在有序集合中快速定位目标值的算法。它的核心思想是“分而治之”每次比较中间元素根据比较结果将搜索范围缩小一半。时间复杂度是O(log n)这意味着对于一个有10亿个元素的有序数组你最多只需要比较30次左右就能找到答案效率极高。无论是面试中的高频考点还是实际开发中处理日志时间戳、用户ID范围、配置表查询等场景二分查找都是你必须熟练掌握的基本功。本文适合所有正在学习算法、准备技术面试或希望优化代码中查找逻辑的开发者。我们将从最基础的原理讲起一步步推导出那个“万能模板”并通过多个变种问题让你真正掌握其精髓。2. 二分查找的核心思想与“坑点”全解析2.1 算法本质不只是“找数字”很多人对二分查找的理解停留在“在一个有序数组里找一个数”。这没错但太片面了。二分查找更本质的是一种基于“有序性”和“单调性”进行快速决策的框架。这里的“有序”不一定是数字大小可以是任何满足单调关系的属性比如时间先后、版本号大小、任务优先级等。算法利用这种单调性通过一次比较就能果断地抛弃一半不可能存在答案的搜索空间。举个例子想象你在翻一本厚厚的字典找单词。你不会从第一页开始一页页翻而是先打开中间一页看看上面的单词。如果你要找的单词按字母序在这页单词之后那么前半本书就可以完全不用看了反之亦然。你不断重复这个过程每次都能扔掉一半的页数。这就是二分查找最直观的体现。2.2 那些年我们踩过的“边界”之坑二分查找的代码框架看似简单但细节是魔鬼。几乎所有错误都集中在循环条件和边界更新上。下面我罗列几个最常见的“坑”你看看自己中过几个循环条件不清晰到底用while (left right)还是while (left right)这是第一个分水岭。前者对应的搜索区间是闭区间[left, right]后者是左闭右开区间[left, right)。选择不同后续的边界更新和返回值处理就完全不同。中间值计算溢出计算中间索引时很多人会写mid (left right) / 2。这在left和right都是很大的整数时left right可能会超出整型范围导致溢出。正确的写法是mid left (right - left) / 2。边界更新死循环在while (left right)的框架下如果你在目标值大于中间值时执行left mid而在某些情况下mid的计算结果始终等于left那么left就永远不会更新导致死循环。例如left 3, right 4时mid 3如果条件分支让left mid则left还是3陷入无限循环。返回值意义混淆循环结束后left和right指向哪里是目标值的位置还是第一个大于目标值的位置或者是插入位置如果不清楚循环不变量的意义根本无法确定返回哪个变量。这些坑的根源在于没有明确定义搜索区间和循环不变量。接下来我们就从这两个核心概念出发构建一个牢固的思维框架。3. 构建思维基石搜索区间与循环不变量3.1 明确你的“搜索空间”两种区间定义在动笔写代码之前你必须先想清楚你定义的left和right初始值代表的是一个什么样的区间这个区间在整个循环过程中需要始终保持一个不变的性质循环不变量。第一种闭区间[left, right]定义left和right都指向有效的、可能包含答案的索引。初始化left 0,right nums.length - 1。循环条件while (left right)。因为当left right时区间[left, right]仍然包含一个元素有必要进行最后一次检查。边界更新如果nums[mid] target说明目标值只可能在右边且mid本身已经检查过不是目标所以新的左边界是mid 1。如果nums[mid] target说明目标值只可能在左边且mid本身已经检查过不是目标所以新的右边界是mid - 1。循环结束当left right时搜索区间为空说明目标不存在。第二种左闭右开区间[left, right)定义left指向可能包含答案的索引right指向的是不包含在搜索空间内的第一个索引类似于迭代器的end()。初始化left 0,right nums.length。注意right初始值等于数组长度因为它指向的是“尾后”位置。循环条件while (left right)。当left right时区间[left, right)已经为空没有元素需要检查。边界更新如果nums[mid] target目标在右边mid已检查非目标新左边界left mid 1。如果nums[mid] target目标在左边但注意right是开区间它指向的是不包含的位置。mid已经比目标大所以新的右边界应该把mid排除在外即right mid。循环结束当left right时搜索区间为空。实操心得我强烈建议初学者甚至是有经验的开发者在解决新问题时优先使用左闭右开区间[left, right)。原因有三第一它的边界更新逻辑更统一left mid 1和right mid不容易出错第二它处理“寻找边界”类问题如第一个大于等于target的位置时更加自然第三它的结束条件left right直接指向一个非常有意义的位置通常是插入位置或边界便于后续处理。在后续的“万能模板”中我们也将基于此区间定义。3.2 循环不变量你的算法“信仰”循环不变量是指在循环开始前、每次迭代后都保持不变的条件。对于二分查找我们的循环不变量就是目标值如果存在一定在当前定义的搜索区间内。在[left, right)区间定义下这个不变量就是在每一轮循环开始时目标值target如果存在于数组中那么它的索引i一定满足left i right。我们所有的边界更新操作都必须维护这个不变量。当nums[mid] target时我们知道target不可能在[left, mid]区间因为数组有序所以将left更新为mid 1新的区间[mid1, right)依然包含target如果存在。当nums[mid] target时注意这里用了这是寻找左边界的关键我们知道target可能在[left, mid]区间但mid本身可能是目标也可能是第一个大于目标的值。为了保持区间左闭右开我们将right更新为mid新区间[left, mid)依然可能包含target如果target存在且mid是第一个等于target的位置那么target的实际索引就是mid但我们的区间是[left, mid)不包含mid这会不会矛盾不这恰恰是我们寻找“左边界”的意图我们让区间不断向左收缩直到锁定边界。最终left会指向那个边界。想明白了搜索区间和循环不变量代码怎么写就变成了一个按部就班的填空题。下面我们就来揭晓那个“万能模板”。4. 二分查找万能模板解析与实现这个模板的核心是处理三种最常见的二分查找场景1查找精确值2查找左边界第一个大于等于target的值3查找右边界最后一个小于等于target的值。我们将用一个统一的框架来应对。4.1 模板代码与注释/** * 二分查找万能模板 * param nums 有序数组假设为非递减 * param target 目标值 * return 根据场景不同返回索引值。未找到时返回-1或插入位置。 */ public int binarySearch(int[] nums, int target) { // 防御性编程 if (nums null || nums.length 0) { return -1; // 或根据场景返回0 } int left 0; int right nums.length; // 注意使用左闭右开区间 [left, right) // 循环不变量目标值若存在其索引i一定满足 left i right while (left right) { // 防止溢出 int mid left (right - left) / 2; // ********** 核心决策逻辑 ********** // // 场景1查找精确值 (标准二分查找) // if (nums[mid] target) { // return mid; // } else if (nums[mid] target) { // left mid 1; // } else { // right mid; // } // 场景2查找左边界 (第一个 target 的元素) if (nums[mid] target) { right mid; // 目标在左半部分包括mid本身因为mid可能就是要找的左边界 } else { left mid 1; // 目标在右半部分 } // 场景3查找右边界 (最后一个 target 的元素) // 通常转化为“查找第一个 target 的元素”然后将其索引减1 // if (nums[mid] target) { // left mid 1; // 目标在右半部分包括mid // } else { // right mid; // } // 循环结束后left是第一个target的位置left-1就是最后一个target的位置 } // 循环结束left right // 对于查找左边界场景2 // left 指向第一个 target 的位置。 // 需要检查 left 是否越界以及 nums[left] 是否等于 target。 if (left nums.length || nums[left] ! target) { return -1; // 未找到目标值 } return left; // 对于查找精确值场景1在循环内已返回。 // 对于查找右边界场景3返回 left - 1并同样需要检查有效性。 }4.2 模板逐行解读与设计逻辑初始化 (right nums.length)我们坚持使用左闭右开区间[left, right)。right初始化为数组长度意味着整个数组都在初始搜索空间内。循环条件 (while (left right))只要区间不为空left right就继续搜索。当left right时区间变为[left, left)这是一个空区间循环结束。中间值计算 (mid left (right - left) / 2)这是防止整数溢出的标准写法。在Java、C等语言中(left right) / 2在两者之和超过Integer.MAX_VALUE时会溢出变成负数导致计算错误。left (right - left) / 2在数学上等价但避免了加法溢出。核心决策逻辑这是模板的灵魂需要根据具体场景调整if判断条件。查找左边界 (第一个 target)使用if (nums[mid] target)。为什么是因为我们的目标是找到第一个大于或等于target的位置。当nums[mid]等于target时它可能就是我们要找的左边界但我们不能直接返回因为左边可能还有更早的等于target的元素。所以我们将right设为mid在左侧区间[left, mid)中继续寻找。这个操作保证了right的左边包括right指向的位置始终满足 target。最终当区间收缩到一点时left就指向了第一个满足 target的位置。查找精确值在循环内判断相等并返回。这是最基础的变体。查找右边界模板中注释了另一种逻辑。通常寻找最后一个 target的元素可以转化为寻找第一个 target的元素然后将其索引减1。代码中当nums[mid] target时说明目标在右边包括mid所以left mid 1。循环结束后left指向第一个 target的位置那么left - 1就是最后一个 target的位置。边界更新这是维护循环不变量的关键步骤。当条件满足如nums[mid] target我们将right更新为mid。因为mid可能已经是或超过了目标边界新的搜索区间[left, mid)仍然可能包含我们要找的边界。当条件不满足如nums[mid] target我们将left更新为mid 1。因为mid已经明确小于目标它绝不可能是我们要找的位置所以从mid1开始搜索。后处理循环结束后left和right相等。这个位置的意义取决于你的决策逻辑。对于查找左边界left是第一个 target的索引。你需要检查①left是否等于数组长度意味着所有元素都小于target②nums[left]是否等于target如果只想找等于target的左边界。根据检查结果返回left或-1。对于查找右边界left是第一个 target的索引那么left - 1就是最后一个 target的索引。同样需要检查left - 1是否越界left 0以及值是否匹配。注意事项这个模板的美妙之处在于你只需要修改核心决策逻辑中的比较条件nums[mid]和target的关系以及最后的返回值处理就能适应绝大多数二分查找问题。再也不用为left、right怎么变而头疼了。5. 实战演练用模板解决三类经典问题理论说得再多不如代码跑一遍。我们直接用上面的模板来解决LeetCode上最经典的三个二分查找问题。我会展示如何将模板“套用”进去并解释每一步的思考过程。5.1 案例一基础查找LeetCode 704题目给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果目标值存在返回下标否则返回-1。分析这是最标准的二分查找查找精确值。我们可以在循环内部判断相等并直接返回。模板应用class Solution { public int search(int[] nums, int target) { if (nums null || nums.length 0) return -1; int left 0, right nums.length; // [left, right) while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; // 找到直接返回 } else if (nums[mid] target) { left mid 1; // 目标在右侧 } else { right mid; // 目标在左侧 } } // 循环结束未找到 return -1; } }要点在找到精确匹配时立即返回这是与寻找边界问题的主要区别。循环内的else分支对应nums[mid] target此时更新right mid。5.2 案例二寻找左边界LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 - 找起始位置题目找出给定目标值在数组中的开始位置。如果不存在返回-1。分析这等价于寻找第一个 target的元素位置并且需要验证该位置的值是否等于target。模板应用class Solution { public int[] searchRange(int[] nums, int target) { int start findLeftBound(nums, target); if (start -1) return new int[]{-1, -1}; int end findRightBound(nums, target); return new int[]{start, end}; } private int findLeftBound(int[] nums, int target) { if (nums null || nums.length 0) return -1; int left 0, right nums.length; // [left, right) while (left right) { int mid left (right - left) / 2; // 核心寻找第一个 target 的位置 if (nums[mid] target) { right mid; } else { left mid 1; } } // 循环结束left是第一个target的位置 // 检查1.是否越界 2.值是否等于target if (left nums.length || nums[left] ! target) { return -1; } return left; } private int findRightBound(int[] nums, int target) { if (nums null || nums.length 0) return -1; int left 0, right nums.length; // [left, right) while (left right) { int mid left (right - left) / 2; // 核心寻找第一个 target 的位置 if (nums[mid] target) { right mid; } else { left mid 1; } } // 循环结束left是第一个target的位置 // 那么 left - 1 就是最后一个 target 的位置 // 检查1. left-1是否越界 2. 值是否等于target if (left - 1 0 || nums[left - 1] ! target) { return -1; } return left - 1; } }要点findLeftBound函数完全使用了模板中的“场景2”逻辑。后处理时left可能是数组长度所有数都小于target也可能指向一个不等于target的数需要检查。findRightBound函数使用了“寻找第一个大于target的位置”的策略。注意if条件变成了nums[mid] target。循环结束后left - 1就是我们要的右边界。同样需要检查有效性。5.3 案例三寻找峰值元素LeetCode 162题目峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组nums找到峰值元素并返回其索引。数组可能包含多个峰值返回任何一个即可。你可以假设nums[-1] nums[n] -∞。分析数组无序但根据题意和边界条件我们可以利用局部单调性进行二分。核心是比较nums[mid]和nums[mid1]如果nums[mid] nums[mid1]说明处于上升坡峰值一定在mid右侧包括mid1所以left mid 1。如果nums[mid] nums[mid1]说明mid本身可能是一个峰值或者处于下降坡峰值在mid左侧包括mid所以right mid。 这依然符合我们“缩小搜索区间”的二分思想。模板应用class Solution { public int findPeakElement(int[] nums) { if (nums null || nums.length 0) return -1; int left 0, right nums.length - 1; // 注意这里用闭区间更方便处理mid1 while (left right) { // 循环直到 left right int mid left (right - left) / 2; if (nums[mid] nums[mid 1]) { // 上坡峰值在右侧 left mid 1; } else { // 下坡或峰顶峰值在左侧包含mid right mid; } } // 当 left right 时即为我们找到的一个峰值索引 return left; } }要点这个问题展示了二分查找不局限于“有序数组”只要存在某种单调性这里是局部单调性沿着某个方向走一定能找到峰值就可以使用二分来快速逼近答案。我们调整了比较对象nums[mid]和nums[mid1]但边界更新的逻辑内核与模板一致。6. 避坑指南与高频问题排查即使有了模板在实际编码和调试中还是会遇到一些典型问题。下面是我总结的“踩坑实录”和解决方案。6.1 问题一死循环现象程序在某个测试用例上永远运行不结束。根因边界更新不当导致搜索区间无法继续缩小。最常见于while (left right)且更新语句为left mid的情况。案例在[left, right)区间left 0, right 1计算mid 0。如果分支判断让left mid则left仍为0区间不变陷入死循环。解决牢记模板的更新规则在[left, right)下left的更新一定是mid 1right的更新一定是mid。这能保证区间每次迭代至少缩小1。6.2 问题二返回结果错误或漏掉元素现象对于某些边界情况如目标值在数组开头、结尾或不存在时返回的索引错误。根因后处理逻辑不完整或循环条件选择错误。排查清单检查初始区间确认right的初始化是nums.length左闭右开还是nums.length - 1闭区间必须与循环条件匹配。检查循环结束后的状态画出区间收缩的最终状态。对于左边界查找循环结束后left指向第一个 target的位置。你需要思考如果所有元素都小于targetleft会等于nums.length。你的代码处理了吗如果left在数组范围内但nums[left] ! target说明target不存在。你的代码返回-1了吗单步调试用最少的元素如空数组、单元素数组、两个元素数组和边界值目标值小于最小值、等于某个值、大于最大值作为测试用例在脑中或纸上模拟代码运行。6.3 问题三如何选择while (left right)还是while (left right)这是一个哲学问题但模板给出了明确答案统一使用while (left right)和左闭右开区间[left, right)。一致性所有二分问题找精确值、找左边界、找右边界都可以用这套框架解决只需修改核心判断条件和后处理。简洁性循环结束条件left right指向的位置通常就是答案或答案的相邻位置语义清晰。减少错误避免了在while (left right)循环结束后还需要纠结left和right哪个是答案的麻烦。当然如果你对闭区间[left, right]非常熟悉并且能保证不出错继续使用也可以。但从教学和统一心智模型的角度我强烈推荐左闭右开区间。6.4 一份自检清单在写完二分查找代码后问自己以下几个问题数组为空或为null时我的代码能处理吗目标值比所有元素都小或都大时返回值正确吗目标值不存在但数组中有其他值时返回值是-1吗数组中有重复的目标值时我是在找第一个还是最后一个还是任意一个我的mid计算方式防止溢出吗我的循环在left和right相邻时能正常退出吗把这几个问题过一遍能帮你排除90%的二分查找Bug。7. 模板的变通与高阶应用场景万能模板不是死板的教条理解其原理后你可以灵活变通解决更复杂的问题。7.1 在非整数域上的二分二分答案二分查找的思想可以应用于任何具有单调性的函数寻找满足某个条件的边界值。典型问题是“二分答案”。例如LeetCode 410 “分割数组的最大值”LeetCode 875 “爱吃香蕉的珂珂”。核心思路确定搜索范围[left, right]这个范围是答案可能的最小值和最大值。定义一个判定函数check(mid)判断当答案是mid时是否满足题目要求。这个函数需要基于题目逻辑实现并且具有单调性如果mid满足那么所有大于或小于mid的值也可能满足。在while (left right)循环中计算mid根据check(mid)的结果按照模板更新left或right。循环结束后的left或right就是所求的答案。示例框架// 假设我们要找满足条件的最小值 int left minPossibleAnswer; // 答案下界 int right maxPossibleAnswer; // 答案上界 while (left right) { int mid left (right - left) / 2; if (check(mid)) { // mid 满足条件说明答案可能 mid向左搜索包含mid right mid; } else { // mid 不满足条件说明答案必须 mid向右搜索 left mid 1; } } // 循环结束left 是满足条件的最小值 return left;7.2 在复杂数据结构上的应用二分查找的关键是“随机访问”中间元素。因此只要数据结构支持O(1)时间的索引访问就可以应用。例如数组最直接的应用。内存中的连续数据结构如ArrayList。通过索引映射的虚拟数组例如在一个已知最大值和单调性的数学函数上寻找解。对于链表等不支持随机访问的数据结构二分查找的O(log n)优势就不复存在了因为访问中间节点需要O(n)时间。7.3 与其它算法结合二分查找常作为子过程嵌入更复杂的算法中快速选择算法在快速排序的 partition 过程中通过比较 pivot 的索引与目标索引决定对哪边进行递归类似于二分。二叉搜索树BST的查找过程本身就是二分思想在树形结构上的体现。数据库索引B树索引的层间查找本质上也是多路二分。掌握二分查找的模板不仅仅是学会了一个算法更是掌握了一种高效缩小问题规模的思维方式。这种思维是优化算法、降低时间复杂度的利器。我个人的体会是初期死记硬背这个模板在各类题目中反复套用、调试、理解。当熟练到一定程度后你就不再需要“背”了因为你对搜索区间和循环不变量的理解已经深入骨髓可以针对任何变种问题迅速推导出正确的代码。这大概就是所谓“无招胜有招”的境界吧。最后一个小技巧在面试中如果你被问到二分查找可以先和面试官明确你使用的区间定义“我习惯使用左闭右开区间”然后基于此展开书写和解释这会让你的思路显得非常清晰和专业。
算法精解与面试技巧)
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
