折半查找法也叫二分查找法几乎是每个学编程的人绕不过去的经典题型。不管你是准备校招笔试、考研复试还是单纯想把算法基础打扎实这个算法都属于那种“看起来简单一写就错”的典型代表。我见过太多人能把原理背得滚瓜烂熟——有序数组、取中间值、比较大小、缩小范围但真到了手写代码的时候边界条件、while循环的终止条件、mid的取值方式每一个细节都能写出一堆bug来。这篇文章我就想把自己在实际刷题和项目里用折半查找法的经验拆开讲讲包括它为什么高效、适用场景有哪些、怎么写才能一次写对、常见变体怎么应对以及我踩过的那些坑。内容尽量照顾到不同基础的读者你要是刚接触这个算法可以从头到尾读一遍要是已经会了基本写法可以直接跳到后面的边界处理和变体题型部分那里才是真正容易翻车的地方。1. 内容整体设计与思路拆解1.1 折半查找法到底是什么折半查找法是在一个有序数组中查找目标值的高效算法。它的核心思路很简单每次取数组的中间位置元素与目标值比较如果中间元素正好等于目标值直接返回如果中间元素大于目标值说明目标值只可能出现在左半部分于是把搜索范围缩小到左半区如果中间元素小于目标值说明目标值只可能出现在右半部分于是把搜索范围缩小到右半区。每次比较之后搜索范围就缩小一半所以叫“折半”。这个思路用生活化的例子来理解最像的就是猜数字游戏。比如一个人心里想了一个1到100之间的整数你每次猜一个数对方告诉你“大了”还是“小了”。最高效的策略不是从1开始一个个往上猜而是每次都猜当前范围的正中间那个数。先猜50如果大了范围就变成1到49如果小了范围就变成51到100。这样每次都能排除掉一半的错误答案最多猜7次就能确定结果。折半查找法就是这个猜数字策略在数组里的正式版本。但这里有一个关键前提也是很多初学者最容易忽略的点数组必须是有序的。如果数组是无序的折半查找法就失效了因为中间值的大小关系不能帮助我们判断目标值在哪一侧。这也是为什么在实际工程里如果需要频繁查找通常的做法是先排序再二分或者直接使用哈希表而不是在一个无序数组上强行套二分。1.2 为什么折半查找法效率这么高折半查找法的时间复杂度是O(log n)。这里的log是以2为底的对数意味着每进行一次比较搜索范围就减半。对于一个有10亿个元素的有序数组最坏情况下只需要约30次比较就能找到目标值。相比之下线性查找最坏需要10亿次比较这个差距在数据量大的时候是毁灭性的。这个效率优势的本质是指数增长的对数化处理。2的30次方约等于10亿也就是说通过30次二分操作就能覆盖10亿个元素。这种“翻倍式缩小范围”的策略不仅在查找问题里有效在很多算法题里都蕴含着同样的思想比如快速幂、二分答案、树状数组等等。所以学会折半查找法学的不只是一个孤立的算法而是一种“每次排除一半”的思维方式。我在实际刷题过程中逐渐意识到折半查找法还有两个隐性优势。第一它的空间复杂度是O(1)只需要几个变量记录左右边界和中间位置不需要借助额外的存储空间。第二它的代码逻辑与硬件缓存机制比较友好因为访问数组元素是连续区间内跳跃式的相比链表这类非连续存储结构cache命中率更高。当然这个优势在数据量不大的时候感知不明显但在海量数据场景下是有意义的。1.3 这个方法适合解决什么问题折半查找法适合解决的问题首要条件是数据具有“有序性”或“单调性”。严格来说不一定是数组已经排好序而是问题本身可以抽象成一个单调函数在这个函数上查找某个边界值。比如在升序数组里找第一个大于等于目标值的位置在降序数组里找最后一个小于等于目标值的位置这些都是折半查找法的变体。我把常见的适用场景归纳为这么几类在有序数组中查找指定的值返回下标或布尔结果。在有序数组中查找目标值的左边界第一个等于目标值的下标或右边界最后一个等于目标值的下标。在有序数组中查找目标值应该插入的位置即第一个大于等于目标值的下标。在某个单调区间内二分答案比如求平方根、求满足某条件的最小值或最大值。在旋转有序数组中查找目标值或者寻找旋转数组中的最小值。在二维矩阵中查找目标值如果矩阵的行和列都有序可以用类二分策略。所以不要只把折半查找法局限在“数组里找一个数”这个层面它背后的单调性思维才是精华所在。遇到一个新问题时如果能抽象出一个单调的判定函数那么大概率可以用二分求解。2. 折半查找法的核心细节与实操要点2.1 经典实现的基础写法先把最标准的迭代版本写出来这是所有变体的基础。我用C和Java风格的写法展示Python的原理完全一样只是语法略有不同。int binarySearch(vectorint nums, int target) { int left 0; int right nums.size() - 1; 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 - 1; } } return -1; }这段代码有几个细节值得仔细品味。第一while循环的条件是left right表示搜索区间是闭区间[left, right]包含两个端点。当left和right相等时区间里还有一个元素没有检查所以循环还要继续。当left right时区间为空说明目标值不存在循环结束。如果用left right作为条件那是在[left, right)这种左闭右开区间下使用的两种写法对应不同的区间定义千万不要混用。第二mid的计算方式是left (right - left) / 2而不是(left right) / 2。原因是left right在极端情况下可能溢出int的范围。虽然一般题目里数组长度不会达到那么大但在实际工程中这是一种好习惯而且写起来也不费事。这个细节在很多面试官眼里是加分项。第三当nums[mid] target时说明目标值在右半部分下一轮搜索范围应该是[mid 1, right]因为mid这个位置已经比较过了确定不是目标值可以安全排除。同理当nums[mid] target时下一轮搜索范围是[left, mid - 1]。这里最容易犯错的地方就是把mid本身又纳入下一轮搜索范围导致死循环。2.2 递归版本的写法与适用场景折半查找法也可以用递归来写并且更容易让初学者理解整个查找流程。递归版本的核心逻辑与迭代版本完全一致只不是通过函数自身调用来实现范围的缩小。int binarySearchRecursive(vectorint nums, int target, int left, int right) { if (left right) { return -1; } int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { return binarySearchRecursive(nums, target, mid 1, right); } else { return binarySearchRecursive(nums, target, left, mid - 1); } }递归版本的优点是逻辑清晰和“每次缩小一半”的数学描述完美对应适合在教学和演示场景下使用。但它的缺点也很明显递归调用会占用函数调用栈空间递归深度为O(log n)在极端情况下可能导致栈溢出虽然log n的深度通常不会很大但在一些对空间要求苛刻的场景下迭代版本是更好的选择。我在实际刷题时一般默认用迭代版本因为不需要额外的函数调用开销也避免了递归边界处理的潜在失误。但在分析算法思路或者给别人讲解的时候会先用递归版本展示核心逻辑再改成迭代版本。这两种写法建议都能手写出来面试时如果时间允许可以先讲递归思路再写迭代代码会显得思路特别清晰。2.3 一个容易忽视的区间定义问题折半查找法的代码看起来都差不多但不同写法背后的区间定义决定了循环条件和边界更新的方式。最常用的两种区间定义是闭区间[left, right]和左闭右开区间[left, right)。闭区间写法我们已经看过了循环条件是left right初始right size - 1更新时left mid 1或right mid - 1。左闭右开区间的写法如下int binarySearch2(vectorint nums, int target) { int left 0; int right nums.size(); // 注意这里不是 size - 1 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; }在这个写法里搜索区间是[left, right)right指针指向的是数组末尾的下一个位置也就是一个无效位置所以循环条件是left right而不是left right。当需要向左收缩时right mid因为mid这个位置已经检查过了但为了保持右开区间的性质right指向的下标不参与搜索所以直接把mid赋值给right就能把mid排除掉。这两种写法各有拥趸没有绝对的好坏。但有一个建议在一道题里从头到尾保持一致。不要闭区间写法里用right mid或者左闭右开写法里用right mid - 1那样会让边界混乱非常容易出bug。我自己偏向闭区间写法因为更直观初始条件好理解查找目标值的标准题用闭区间最顺手。但如果是实现C标准库里的lower_bound、upper_bound这些函数原生的思路更接近左闭右开区间。所以两种写法都得熟练。2.4 二分查找的三个“不变量”我后来复盘错题时总结出二分查找代码里最重要的三个不变量。所谓不变量就是在循环过程中始终保持正确的性质一旦有一个环节破坏了不变量程序就会出错。第一个不变量目标值一定位于当前搜索区间内。初始时这个性质成立因为整个数组是有序的且目标值存在与否未知我们假设目标值可能在任意位置所以初始化成整个数组范围。每次迭代后如果确定目标值不等于mid位置的元素就把mid排除然后选择目标值可能存在的那一半性质依然保持。第二个不变量搜索区间的长度在逐渐缩小。每一轮迭代mid总会在当前区间内取到然后无论是left mid 1还是right mid - 1搜索区间的长度都至少减少1。这个性质保证了循环一定会终止不会陷入死循环。第三个不变量mid永远取当前区间的中间位置。这个看起来是废话但很多错误恰恰是在这里产生的。比如有的写法是left mid而不是left mid 1在区间长度为2的时候mid left (right - left) / 2算出来等于left如果此时nums[mid] target更新left mid后区间没能缩小就死循环了。理解这三个不变量之后再看网上各种二分模板就不会晕了。不管模板怎么变本质上都是在维护这三个性质区别只是区间开闭和边界更新的具体表达形式。3. 实操过程与核心环节实现3.1 用具体数据走一遍查找流程理论讲再多也不如手推一遍数据来得直接。我假设有一个有序数组nums [1, 3, 5, 7, 9, 11, 13, 15]要查找的目标值target 7。初始化状态left 0right 7搜索区间是[0, 7]。第一轮迭代mid 0 (7 - 0) / 2 3nums[3] 7。比较nums[3]和target发现正好相等直接返回3查找结束。这次运气好一次就命中了。再来看一个稍微曲折一点的例子查找target 11。初始化状态left 0right 7搜索区间是[0, 7]。第一轮迭代mid 3nums[3] 7。7 11说明目标值在右半部分更新left mid 1 4。当前搜索区间变成[4, 7]。第二轮迭代mid 4 (7 - 4) / 2 5nums[5] 11。11 11命中返回5。再来看一个查找不存在的值的情况查找target 10。初始化状态left 0right 7。第一轮mid 3nums[3] 77 10更新left 4区间[4, 7]。第二轮mid 5nums[5] 1111 10更新right 4区间[4, 4]。第三轮mid 4nums[4] 99 10更新left 5。此时left 5right 4left right循环条件left right不满足退出循环返回-1说明目标值不在数组中。这三条路径基本覆盖了查找成功、查找靠右、查找失败三种情形。走完这三个例子对循环条件和边界更新的信任感会强很多。我教别人的时候也喜欢让对方先在纸上手动模拟一遍再上机器跑代码理解深度完全不一样。3.2 实际代码中的输出验证与测试用例设计写完了代码之后测试是重中之重。不要只测一个数组、一个目标值就完事那远远不够。我每次写完二分查找都会把测试用例分成几组来跑。第一组是边界位置测试有序数组里查找第一个元素查找最后一个元素。比如nums [1, 3, 5, 7, 9]target 1应该返回0target 9应该返回4。这两个用例最容易测出初始边界设置的问题。第二组是数组长度为1的测试nums [5]target 5应该返回0target 3应该返回-1。这个用例主要看while循环条件是否正确以及mid计算是否越界。第三组是空数组测试nums []任何target都应该返回-1。这个用例最容易暴露代码对空输入是否足够健壮。第四组是重复元素的测试nums [1, 2, 2, 2, 3, 4]如果只是基本的查找返回任何一个等于2的下标都算正确。但如果是变体题型比如找左边界、右边界结果必须精确。第五组是超大数据量的测试构造一个长度为10的6次方量级的有序数组随机选目标值验证代码能在极短时间内返回结果同时观察是否存在溢出问题。这个测试能帮助你验证mid计算公式是否安全。我在本地调试的时候会写一个非常简单的测试框架把测试用例和预期结果放在一个vector里循环跑完所有用例并自动比对输出。这样每次修改代码后一条命令就能知道有没有回归问题效率极高。3.3 在排序数组中查找目标值的完整示例如果只是写一个单独的查找函数那这题就算做完了。但在实际面试和笔试里很多时候题目会变成给定一个排序数组和一个目标值找出目标值在数组中出现的开始位置和结束位置。这就是经典的“在排序数组中查找元素的第一个和最后一个位置”问题其实本质就是查找左边界和右边界。我第一次接触这道题的时候想着能不能在一次二分里同时找到左右边界折腾了很久代码越写越复杂最后还是老老实实分别二分。但其实这两次二分可以共用一套框架只是在条件判断上略有区别。vectorint searchRange(vectorint nums, int target) { if (nums.empty()) { return {-1, -1}; } int leftBound findLeftBound(nums, target); if (leftBound -1) { return {-1, -1}; } int rightBound findRightBound(nums, target); return {leftBound, rightBound}; } int findLeftBound(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } if (left nums.size() nums[left] target) { return left; } return -1; } int findRightBound(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } if (right 0 nums[right] target) { return right; } return -1; }这段代码里最关键的地方在于查找左边界时nums[mid] target的情况被归类到right mid - 1这一分支也就是说即使找到了目标值也会继续向左搜索直到区间为空。循环结束后left指向的位置就是第一个等于target的位置。如果不存在目标值left可能指向一个不等于target的位置也可能越界所以通过left nums.size()且nums[left] target来判断是否真的找到了目标值。查找右边界的逻辑正好对称nums[mid] target时被归类到left mid 1分支持续向右搜索循环结束后right指向的就是最后一个等于target的位置。这个模板帮我解决了很多变体题目后续遇到的“查找插入位置”问题、查找峰值问题本质上都是左边界或右边界模板的变形。建议把这两个子函数单独拎出来练熟。3.4 用二分查找解决一个非数组问题二分查找的应用范围远不止数组本身。我拿“求一个非负整数的算术平方根”来举个例子。题目要求在不使用内置sqrt函数的前提下计算目标值的整数平方根结果向下取整。这个问题的思路是在[0, x]区间内二分搜索一个整数mid使得mid的平方小于等于x但(mid1)的平方大于x。这里的单调性非常明确mid越大mid的平方越大。于是可以直接套用右边界模板。int mySqrt(int x) { if (x 0) { return 0; } if (x 1) { return 1; } int left 1, right x / 2 1; while (left right) { int mid left (right - left) / 2; if ((long long)mid * mid x) { left mid 1; } else { right mid - 1; } } return right; }这里有几个细节值得注意。第一right的初始值设为x / 2 1而不是x因为一个大于等于2的数的平方根一定不超过x/2这个初始化缩小了搜索范围虽然时间复杂度不变但能让循环更快结束。第二mid * mid可能溢出int范围所以用(long long)强制转换这是很多笔试里容易踩的坑。第三循环结束后right指向的是最后一个满足mid * mid x的位置直接返回right就是答案。通过这个例子可以看到二分的核心是在一个单调的判定函数上查找边界。只要能写出一个好的判定函数很多看似和数组没有关系的问题都能转化成二分问题。4. 常见问题与排查技巧实录4.1 死循环问题最常见的翻车原因死循环是二分查找里最常见的bug新手老手都有可能遇到只是原因不同。死循环的表现是程序在while循环里一直出不来CPU占用率飙升最后超时。死循环的触发原因通常有两个。第一是边界更新不正确比如在left需要前进的时候写了left mid而不是left mid 1。前面提到当区间长度为2的时候mid计算出来等于left如果此时left mid整个区间没有缩小就死循环了。第二是while循环条件和mid计算公式的组合出了问题比如左闭右开区间写法下如果循环条件写成left right而right初始值是size那么当left和right相等的时候mid可能访问到数组越界的位置。解决死循环问题的最好办法不是靠猜而是打印调试。我一般在while循环开头加一行输出打印当前的left、right、mid三个变量跑一次测试用例就能很直观地看到边界是怎么变化的。通常打印几轮就能发现哪个变量没有按照预期变化。另外还有一个百试百灵的技巧把区间长度缩小到2或者3手动在纸上模拟一遍。比如nums [1, 3]target 3一步步算马上就能发现死循环的原因。这个技巧在面试现场尤其好用不用打开电脑一支笔一张纸就能完成排查。4.2 越界问题mid 的计算与访问越界问题分成两种一是访问数组时下标越界二是mid的计算过程本身溢出。访问数组越界最常见的原因是while循环条件写错。比如数组长度是10right初始化为10在左闭右开区间写法中循环条件应该是left right这样当left right的时候循环退出就不会访问nums[10]。但如果把循环条件写成left rightleft和right可以相等此时mid可能等于10访问nums[10]就崩了。还有一种情况是查找左边界的时候循环结束后left可能超出数组末尾此时如果直接用left作为下标去访问nums[left]就会越界。所以必须加一个left nums.size()的判断再结合nums[left] target来判断结果是否有效。同理查找右边界时right可能是-1需要判断right 0。mid计算溢出是另一个隐蔽问题。当left和right都很大的时候(left right) / 2有可能超过int能表示的最大值导致结果变成负数或者错误的值。解决办法就是写成left (right - left) / 2这个写法的数学结果和(left right) / 2一样但避免了中间加法溢出。我在写所有二分相关代码时一律使用这种写法已经形成肌肉记忆了。4.3 结果不准确问题左边界和右边界的混淆有些题目里数组存在重复元素要求返回第一个等于目标值的位置或者最后一个等于目标值的位置。如果还用最基本的查找逻辑找到一个等于目标值的mid位置就直接返回那么返回的下标不一定是边界位置。比如nums [1, 2, 2, 2, 3, 4]target 2。基本查找可能在第一次迭代中mid指向下标2返回2。但这个数组里第一个等于2的是下标1最后一个等于2的是下标3。如果题目要求返回边界这个结果就是错的。我踩过这个坑之后总结出经验遇到要求边界的问题不要试图在一次二分里兼顾左右两边直接用左边界模板找一次再用右边界模板找一次代码更清晰也更容易验证正确性。还有一类问题是返回“插入位置”的题目即给定一个有序数组和一个目标值如果目标值存在就返回其下标如果不存在就返回它应该被插入的位置。这个问题本质上就是查找第一个大于等于目标值的位置直接套左边界模板循环结束后left就是答案。这类题目最容易出错的地方是边界情况比如目标值比数组所有元素都大时left最终会等于nums.size()这恰好是正确的插入位置不能把它当作越界错误处理。4.4 常见错误速查表我把平时在刷题网站评论区和自己学员的代码里看到的高频错误整理成一个表格方便大家对照自查。错误类型错误写法正确写法后果mid计算溢出(left right) / 2left (right - left) / 2大数溢出结果错误闭区间循环条件错误while (left right)while (left right)漏查最后一个元素左边界更新错误left midleft mid 1死循环右边界更新错误right midright mid - 1死循环左开右闭区间下循环条件错误while (left right)while (left right)数组越界空数组未处理直接访问nums[0]判断nums.empty()运行时崩溃查找边界后未校验直接返回left判断范围且nums值相等返回错误下标这个表里的错误我基本都犯过特别是早期学习的时候几乎每一条都踩了一遍。后来我把这个表当作自己的checklist写二分前先过一遍写完后再过一遍大大减少了低级bug。5. 进阶折半查找法的变体与应用扩展5.1 旋转有序数组的查找旋转有序数组是指一个有序数组在某个未知位置进行了旋转比如[1, 2, 3, 4, 5]旋转成[3, 4, 5, 1, 2]。这种数组不具备全局有序性但仍然保留了两个有序段因此还是可以用二分来查找目标值只是判断逻辑更复杂一些。核心思路是每次计算出mid之后先判断左半部分是否有序再判断右半部分是否有序。如果nums[left] nums[mid]说明左半部分是有序的否则右半部分是有序的。然后根据目标值是否落在有序的那半部分决定搜索方向。int searchRotated(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } if (nums[left] nums[mid]) { if (nums[left] target target nums[mid]) { right mid - 1; } else { left mid 1; } } else { if (nums[mid] target target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }这段代码的关键判断是nums[left] nums[mid]而不是nums[left] nums[mid]因为当区间只有两个元素时left和mid可能是同一个位置使用可以保证判断正确。这种细节在写变体题时特别重要拿到的代码要不要处理等值情况直接决定了能否通过边界测试。5.2 C 标准库中的二分函数在C标准库里有一套现成的二分查找函数包括binary_search、lower_bound、upper_bound、equal_range。它们的底层实现就是折半查找法的变体非常值得学习源码思路。lower_bound用于查找第一个大于等于目标值的迭代器upper_bound用于查找第一个大于目标值的迭代器lower_bound和upper_bound之差就是等于目标值的元素个数。binary_search直接判断目标值是否存在等价于先调用lower_bound再比较值是否相等。我平时做题的时候如果题目场景符合这些函数的语义会直接调用省时省力。但在面试中如果题目明确要求手写二分使用库函数不一定被认可。所以我的建议是库函数能帮你提高开发效率但还是要能手写底层实现。最好的练习方式是自己实现一个lower_bound和upper_bound然后用库函数做交叉验证保证自己的实现和标准库结果一致。这里给出一个自己实现lower_bound的参考int lowerBound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } return left; }这个实现采用左闭右开区间循环条件是left right当nums[mid] target时right mid继续向左收缩。循环结束后left指向第一个大于等于target的位置。注意这个实现里没有nums.empty()的判断因为空数组时right 0循环不会进入直接返回0正好是空数组的合法插入位置。5.3 二分答案隐式数组上的折半查找有些问题里我们没有直接给出一个数组但仍然可以应用二分。这种技巧通常被称为“二分答案”。典型的例子包括给定一个距离数组求运货船的最小载重能力给定一个数组求分割数组的最大值最小化给定一排香蕉树求猴子在H小时内吃完所有香蕉的最小速度。这些问题的共同特点是存在一个单调的判定函数check(x)对于x的某个取值条件满足或不满足的边界是确定且唯一的。我们可以在这个单调区间上二分搜索这个边界值。拿“吃完香蕉的最小速度”举例。假设有n堆香蕉每堆数量不同猴子每小时最多吃一堆中的一部分要求在H小时内吃完问最小的速度k是多少。判定函数check(k)表示在速度k下能否在H小时内吃完所有香蕉。这个函数是单调的——速度越大越可能吃完所以可以二分。写出判定函数需要一点数学计算每一堆香蕉在速度k下需要ceil(pile / k)小时把所有堆的时间加起来如果总时间小于等于H说明速度k可行可以尝试更小的速度。二分下界是1上界可以是香蕉堆中的最大值。我之前在给学员讲这个题的时候发现很多人卡在“不知道二分什么”上。其实答案就是二分题目要求的那个量。题目问最小速度就二分速度问最小容量就二分容量问最短天数就二分天数。只要你能写出对应的判定函数整个题目就转化成了一个标准的二分框架问题。5.4 浮点数二分与精度控制前文提到的二分都是针对整数的而实际工程里经常需要在实数范围内做二分。比如求解一个连续函数的零点或者计算某个方程的解都可以用浮点数二分。浮点数二分和整数二分的区别在于循环终止条件。由于浮点数无法通过穷举区间长度来判断是否为空我们通常设置一个精度阈值eps比如1e-7或1e-8当区间长度小于eps时认为已经收敛到足够精度的解退出循环。double binarySearchFloat(double left, double right, double target) { double eps 1e-7; while (right - left eps) { double mid (left right) / 2; if (check(mid, target)) { right mid; } else { left mid; } } return (left right) / 2; }浮点数二分里需要注意一个问题eps不能设置得过小否则循环次数会非常多甚至因为浮点数的表示精度限制而无法收敛。一般1e-6到1e-8是常见的范围如果要更高的精度需要确认题目要求的输出位数通常比输出位数多两位就够了。另外浮点数二分中更新边界时直接把left mid或right mid即可不存在整数二分里的数组越界问题因为mid是区间内部的实数不会出现区间不缩小的尴尬。6. 实操心得与避坑经验总结写到这里我感觉折半查找法能聊的东西还有很多但核心的干货基本都铺开了。最后分享几个我个人的体会和经验希望能在你实际写题时帮上忙。首先动笔写二分前先问自己一句我现在的搜索区间是闭区间还是左开右闭区间这个问题决定了后面所有的边界更新方式。如果一开始就把区间定义明确死循环和越界问题的发生率会大大降低。不要写了一半再琢磨left和right到底该等于mid还是mid加减1那时已经晚了。其次写完二分之后一定要主动跑几个边界用例。我见过太多人写完代码只测一个普通用例比如nums [1, 2, 3, 4, 5], target 3然后就说自己写完了。但真正有区分度的用例往往在边界上数组长度1、目标值比所有元素都小、目标值比所有元素都大、空数组、重复元素。把这几个用例跑通代码才算是基本可靠的。再次遇到变体题比如找左边界、右边界、插入位置不要急着套模板先把题意转化成“第一个大于等于target的位置”或者“最后一个小于等于target的位置”这样精确的语义再对着区间去写。你会发现所有变体题脱掉外壳之后本质上都是标准二分的微小改动。最后也是我最想强调的一点折半查找法虽然代码量很小但它训练的是你对“单调性”的敏感度。在实际工程中很多性能调优、日志搜索、配置项定位本质上都可以用二分的思路来加速。把这个思想吃透远比背下一两段代码有价值得多。我自己的习惯是每隔一段时间就把二分查找的几种典型写法重新手敲一遍包括闭区间基本版、左闭右开版、lower_bound、upper_bound、旋转数组查找就当是热身运动。写的次数多了你会发现这些代码已经变成了肌肉记忆即使隔了很久不碰算法拿到题目也能在三分钟之内写出来。这种熟练度才是应对笔试和面试的底气。