1. 二分查找解决什么问题有一个前提必须知道打卡第三天我把二分法单独拎出来过了一遍。二分法二分查找的基本思想一句话就能说清在有序数据中反复取中间值通过比较把搜索范围砍半。但真正把它写到代码里很多人都会在边界条件上卡住。我自己的真实感受是二分查找难点从来不在“二分”这个动作而在“你定义了一个什么样的区间”以及“每一步该怎么安全缩小这个区间”。这篇内容会从核心思路讲到可直接复制的模板再到左边界、旋转数组、二分答案这些常见变体最后把我踩过的坑和排查方法整理成清单。适合刚开始学算法的读者也适合那种“每次写二分都要现推边界”的同学。1.1 它到底解决什么问题最基础的场景是在一个有序数组里找目标值的下标。比如给你[1, 3, 5, 7, 9, 11, 13, 15]目标值是7。顺序查找要从头扫到尾运气不好要比较8次二分查找先看中间值7一次命中。数组规模小的时候看不出差距但数据量到十万、百万级别顺序查找和二分查找的速度差距是指数级的。生活里最贴近的例子就是猜数字游戏裁判心里想一个1到100之间的数你每次猜一个数对方告诉你“大了”还是“小了”。聪明的人第一次猜50根据反馈把范围砍成1到49或51到100然后继续对半砍。最多7次一定能猜中因为2的7次方是128已经覆盖100种可能。这里有一个前提经常被新手忽略二分查找要求数据是有序的。如果数组是乱序那你比较中间值时既不能确定目标在左半还是右半也不能安全丢弃任何一部分。很多人在LeetCode上好奇“为什么我这个二分结果不对”排查半天发现数组根本没有排序这就是问题根源。如果一定要在无序数组上用二分必须先把数组排序但要注意排序会打乱原始下标。所以工程上如果有“既要查找又要返回原始位置”的需求常规做法是存一个索引数组按值排序索引后再二分。在真实项目里二分查找的“有序”范围也比很多人想象得广数据库索引的查找方式本质上是多路搜索树上的二分跳表里从高层往底层找目标每一层也是二分思想一些流媒体协议做数据包重传也会通过二分定位缺失区间。基础算法的意义就在于它并不只是在刷题场景里有用而是更复杂数据结构的“内嵌逻辑”。1.2 为什么每次排除一半是安全的这是二分查找正确性的核心也是我后来才真正想明白的点。假设当前搜索区间是闭区间[left, right]mid (left right) / 2我们拿nums[mid]和目标值target比较。当nums[mid] target时因为数组是从小到大排列的所以从left到mid的所有元素都小于target它们不可能等于目标值可以整体丢弃。当nums[mid] target时同理mid到right的所有元素都大于target也可以整体丢弃。每一次比较都让我们至少缩小一半的搜索空间这才是“分治”思想的精髓。我经常用一个比较容易理解的说法二分不是“碰运气”而是利用有序性带来的可判定性。当你能够根据一个中间值的大小判断出目标值一定不在某一段时这一段就可以放心扔掉。反过来如果数据不具备这种判定关系比如数组中存在乱序、或者判断函数本身不单调那么扔掉一半就是错误的结果自然不对。在进阶场景里这种“可判定性”不一定要依赖数值的大小关系。比如二分答案类题目我们只是需要判断某个k是否可行并且保证“k可行则更大的k也可行或者k不可行则更小的k也不可行”这种性质叫二段性。只要满足二段性即使数值本身不是严格递增的也可以二分。这一点我会在第三章展开。1.3 时间复杂度为什么是 O(log n)每次把搜索范围缩小一半假设初始范围是n经过k次迭代后范围变成n / 2^k。当范围缩小到只剩一个元素时停止所以有n / 2^k ≈ 1解出来k ≈ log2(n)。这就是为什么二分查找的时间复杂度是O(log n)。它不需要额外数组没有递归栈开销空间复杂度是O(1)这也是它作为基础查找算法经久不衰的原因。很多人对O(log n)这个符号没概念。我举个例子如果你有一个包含10亿个元素的有序数组顺序查找最坏情况要比较10亿次而二分查找最多只需要30次左右因为2的30次方已经超过10亿。这几乎是实时反馈和不可接受的延迟之间的差别。在面试中聊到“为什么有那么多高级数据结构二分查找还是基石”时一般都用这个数量级对比来回答简单有力。2. 手写二分查找的三种模板与边界必杀技说到手写二分很多人第一反应是“我会”但真让他写经常会写出来一个在某些边界情况死循环的版本。我刷题第三天的最大收获是与其每次都现场推导边界不如熟练掌握几种固定模板然后在模板基础上理解循环不变量。下面我会给出三种最常见的写法并解释它们各自适合什么场景。2.1 三种循环写法对比第一种是闭区间写法也是最直观的一种。初始化left 0、right len(nums) - 1循环条件是while left right。这个写法里搜索区间始终是[left, right]当nums[mid] target时直接返回下标当nums[mid] target时说明目标在右半部分执行left mid 1当nums[mid] target时说明目标在左半部分执行right mid - 1。这里有个关键细节mid本身已经比较过了所以缩小范围时必须把mid排除在外否则可能出现left和right永远不动的情况。第二种是左闭右开写法初始化left 0、right len(nums)循环条件是while left right。搜索区间是[left, right)右侧是开区间所以right指向的位置是不参与当前搜索的。这个写法的优势在于处理“查找边界”类问题时特别顺手常见的lower_bound就是用这个模板实现的。当条件满足时移动right mid不满足时移动left mid 1因为开区间右侧天然不包含mid所以不用写mid - 1可以有效避免边界越界。第三种是排除法写法循环条件同样是while left right但中间不判断是否找到目标而是把搜索区间中“不可能存在答案的一半”直接剔除。每次根据某种条件要么left mid 1要么right mid循环退出时left就是答案。这非常适合那些“找最小满足条件的值”或“找旋转数组最小值”的问题。我把三种写法整理成一个简单的对比表方便大家对照模板初始化循环条件区间维护方式适合场景闭区间left0, rightn-1left right比较后缩小区间mid排除标准查找目标值左闭右开left0, rightnleft right满足条件rightmid否则leftmid1查找边界、插入位置排除法left0, rightn-1left right条件分支缩小区间退出即答案峰值、旋转数组、二分答案2.2 溢出问题与防御式写法很多人写二分时有一个疑问mid (left right) // 2和mid left (right - left) // 2到底有什么区别在 Python 里整数不会溢出两种写法结果一样但在 Java、C 这类语言里如果left和right都接近int的最大值left right可能直接溢出成负数然后除以2会得到错误结果。这个问题在刷题时可能不明显但在实际的代码评审里是很容易被指出的点。所以我的习惯是无论用什么语言都写成mid left (right - left) // 2。这个式子保持了向下取整的行为又避免了先加后除带来的溢出风险。理解也不难先算出左右之间的距离再除以2最后把偏移量加到left上。换句话说mid是left走到left和right中点后的位置。还有一个方向容易被忽略如果你采用了“排除法”且某个分支需要让left mid那么必须使用右中位数也就是mid left (right - left 1) // 2。原因是如果区间只剩两个元素左中位数会等于left此时left mid会导致区间完全不缩小陷入死循环而右中位数会等于right配合另一个分支收缩才能保证循环正常退出。这个“向上取整还是向下取整”的选择是二分死循环问题最常见的根源之一。2.3 一个可以日常复用的通用模板如果你不想记太多种模板我推荐主攻“左闭右开 lower_bound”这一套。它对新手更友好因为写法和语义都比较清晰。我贴一下 Python 版的通用模板函数返回第一个不小于target的位置也就是第一个满足nums[i] target的下标def lower_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left这个模板的循环不变量是target第一次可能出现的区间是[left, right)。如果nums[mid] target说明mid及其右边都不可能是“第一个小于 target 的元素”答案可能在mid或更左边所以更新right mid如果nums[mid] target说明mid及左边都不满足条件答案一定在mid右侧所以更新left mid 1。循环退出时left就是第一个大于等于target的位置。如果我们要实现“在数组中查找目标值下标找不到返回 -1”只需要在这个模板基础上加一个校验def binary_search(nums, target): pos lower_bound(nums, target) if pos len(nums) and nums[pos] target: return pos return -1这套模板也可以轻松改成查找target的插入位置也就是 LeetCode 35 的答案lower_bound(nums, target)本身就是插入位置。JavaScript 版本写法几乎一致只是把//换成Math.floorfunction lowerBound(nums, target) { let left 0, right nums.length; while (left right) { const mid left Math.floor((right - left) / 2); if (nums[mid] target) { right mid; } else { left mid 1; } } return left; }我个人建议第一次学习时可以把闭区间写法和左闭右开写法各练熟一个场景但日常刷题时固定使用其中一种。不要每次写二分都重新“发明”边界规则那样很容易出错。3. 二分查找变体左边界、旋转数组与二分答案二分查找真正拉开差距的地方在于变体。LeetCode 上最常考的并不是“在有序数组里找一个数”而是“找左边界”“找右边界”“在旋转数组中找最小值”“用二分答案求最优值”等。第三章我把这些常见变体的思路和模板一一展开。3.1 查找左边界和右边界假设有一个数组[5, 7, 7, 8, 8, 10]要找到第一个8的下标和最后一个8的下标。如果你用标准闭区间二分去找8返回的下标可能是 3 也可能是 4这取决于中间值的取法和比较顺序随机性会导致结果不稳定。正确的做法是用“下界”和“上界”来定位。查找第一个等于target的位置本质上是查lower_bound(nums, target)。如果返回的位置没有越界并且nums[pos] target那么这个pos就是第一个目标值否则说明数组中不存在target。查找最后一个等于target的位置本质上是查第一个大于target的位置然后减 1。这个位置可以用upper_bound求def upper_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return leftupper_bound返回第一个严格大于target的位置所以最后一个等于target的位置就是upper_bound(target) - 1。LeetCode 34 的完整解法就很简洁def search_range(nums, target): first lower_bound(nums, target) if first len(nums) or nums[first] ! target: return [-1, -1] last upper_bound(nums, target) - 1 return [first, last]这个例子很好地说明了为什么要维护“循环不变量”。lower_bound始终在维护“第一个大于等于 target 的位置在[left, right)中”不会因为数组里有多个重复目标而乱跳。以后只要遇到“在排序数组中找区间”“统计某个值的数量”这类问题都可以直接套这两个函数。3.2 旋转数组与部分有序场景旋转数组本身不是完全有序的但它仍然可以二分。比如[4, 5, 6, 7, 0, 1, 2]我们可以把数组分成两段前半段[4,5,6,7]和后半段[0,1,2]每一段内部都是有序的而且后半段的最大值小于前半段的最小值。要找到最小值关键是比较nums[mid]和nums[right]。def find_min(nums): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[right]: left mid 1 else: right mid return nums[left]为什么这里比较nums[right]而不是nums[left]因为nums[mid] nums[right]时能明确最小值在mid的右侧因为右侧出现了比中间值更小的数说明这里发生了旋转而nums[mid] nums[right]时说明mid到right这一段是单调不减的最小值在mid或者mid的左侧。如果你用nums[left]做比较在数组完全没有旋转时容易误判。我第一次写这个题时就犯了这种错在[1,2,3,4,5]上得到错误答案排查了很久才发现是比较对象选错了。如果允许数组中有重复元素比如[2, 2, 2, 0, 1, 2]情况会更复杂。当nums[mid] nums[right]时你无法判断最小值在左还是右常规做法是把right左移一位让范围缩小一点虽然最坏情况会退化到O(n)但平均情况下仍然很快。这个“退化成本”是重复值带来的理论上的最优复杂度就是O(n)所以不必过度纠结。3.3 二分答案与浮点数二分二分答案是我觉得二分思想里最精彩的一类应用。它不对数组下标做二分而是对“答案的取值范围”做二分然后用一个判定函数检查当前取值是否可行。典型题是 LeetCode 875一堆香蕉每堆有piles[i]根你每小时能吃K根求能在H小时内吃完的最小速度。这个问题的答案范围是[1, max(piles)]速度K越小越可能超时越大越可能吃得完所以“是否能在 H 小时内吃完”这个判定函数对K具有二段性可以二分。def can_finish(piles, speed, h): hours 0 for p in piles: hours (p speed - 1) // speed return hours h def min_eating_speed(piles, h): left, right 1, max(piles) while left right: mid left (right - left) // 2 if can_finish(piles, mid, h): right mid else: left mid 1 return left这种写法的核心不是二分本身而是识别出单调性判定函数的结果要么是“满足”要么是“不满足”并且存在一个阈值阈值一侧全部满足另一侧全部不满足。看到这类题第一步不是写二分而是写一个check(k)函数然后判断能不能check(k)推出check(k1)同样满足。如果成立就放心二分。浮点数二分也很常见比如求一个数的平方根。因为浮点数不能精确判断相等通常不写while left right而是用固定迭代次数或者精度差来控制。常见写法如下def my_sqrt(x): left, right 0.0, float(x) for _ in range(100): mid (left right) / 2 if mid * mid x: left mid else: right mid return right这里固定迭代100次每次让区间缩小一半100次之后区间已经缩小到计算机浮点精度无法分辨的程度所以返回值足够精确。用固定次数还有一个好处完全不用处理while循环的终止条件省去了浮点数比较eps的麻烦。4. 打卡第三天实录二分死循环排查与避坑清单刷题打卡第三天我在二分变体上翻过几次车。这些坑非常典型网上搜“二分死循环”能看到相似的提问但很多答案只说了“改中位数取法”没说为什么。我把自己的排查过程和结论整理出来相当于一份可以直接对照的避坑手册。4.1 我实际踩过的三个坑第一个坑是left mid导致死循环。当时我在实现“寻找峰值”相关的逻辑某个分支写的是left mid但mid用的是向下取整。当区间只剩两个元素时mid正好等于left更新后的left还是原来的值区间永远不缩小程序就在循环里出不来了。解决方法是把这一分支改成left mid 1或者把mid改成右中位数left (right - left 1) // 2。核心原则其实很简单每次循环结束后区间必须严格变小否则就是死循环的温床。第二个坑是right的初始值混用。right len(nums) - 1用于闭区间right len(nums)用于左闭右开区间。两边写法看起来很像但如果模板混用结果往往要么漏掉最后一个元素要么访问越界。我见过很多人在lower_bound里把right初始化为len(nums) - 1然后在nums[mid] target时执行right mid。此时如果目标值就是数组最后一个元素right永远到不了len(nums) - 1循环提前退出返回错误位置。这种错很难一眼发现最好的办法是严格区分模板不要混用区间语义。第三个坑是把“任意一个目标位置”当成“第一个目标位置”。在有序数组[1, 2, 2, 2, 3]里找2标准闭区间二分返回的下标可能是 1也可能是 2这取决于中间值的选择。如果题目要求第一个或最后一个就必须用上下界模板。我以为自己已经会了二分但实际做 LeetCode 34 时才意识到这个语义差异有多重要。经验就是先问自己要的是“一个位置”还是“边界位置”再选模板。4.2 排查二分问题的方法论写二分出问题时我推荐一套比较高效的排查流程。第一步找一个长度特别小的数组比如[1, 2, 3, 4, 5]手动模拟left、mid、right的变化过程画一张表。例如查找3初始left0, right4, mid2nums[2]3命中。如果目标换成0left0, right4, mid2nums[2]3 0所以right1继续计算mid0nums[0]1 0所以right-1循环退出返回 -1。手动模拟能很快看出区间是否按预期缩小。第二步用随机数据做对拍测试写一个顺序查找函数然后和二分结果对比。刷题的时候不需要写很复杂的测试框架直接生成随机小数组就够了import random for _ in range(10000): arr sorted(random.sample(range(1000), 50)) t random.randint(0, 999) b binary_search(arr, t) e arr.index(t) if t in arr else -1 if b ! e: print(error:, arr, t, b, e) break这个测试能非常快地暴露边界问题尤其是“第一个位置”和“最后一个位置”这类题目。第三步也是最容易被忽略的用眼睛检查循环不变量。写完代码后在while循环前面写一行注释说明当前区间代表什么比如“[left, right)是答案可能出现的区间”。然后每次更新区间时检查如果条件满足答案是否一定在[left, mid]内如果条件不满足答案是否一定在[mid1, right)内维护好这个语义比死记模板更可靠。4.3 常见问题速查表我整理了一些二分查找的高频问题做成表格放在这里。如果在刷题或面试时突然卡住可以直接对照排查现象可能原因处理方法程序死循环left mid时使用了向下取整区间未严格缩小改成left mid 1或使用右中位数数组越界初始化right用错len(nums)与len(nums)-1混用明确当前模板是闭区间还是左闭右开区间返回结果总是差一位没有维护循环不变量区间语义混乱在循环前写好区间注释逐分支检查溢出风险写成(left right) // 2改为left (right - left) // 2重复值结果随机把“找任意一个”当成“找第一个/最后一个”改用lower_bound/upper_bound模板二分答案不对判定函数没有单调性或check(mid)的阈值方向弄反先验证check(k)是否能推出check(k1)也满足这个表本质上是对我踩坑经验的浓缩。新手阶段直接把表贴在手边每写完一个二分题就对照检查一遍很快就能形成正确的肌肉记忆。4.4 一点个人体会刷题打卡这两天我最大的一个体会是二分查找不是难在“二分”这两个字而是难在“对区间语义的长期维护”。以前我总觉得模板背下来就够了后来发现考试或者面试中只要题干稍微变一下背模板就会翻车。现在我写二分前都会先问自己三个问题初始区间是闭区间还是左闭右开循环退出时left和right分别指向什么位置我要求的是第一个、最后一个还是任意一个满足条件的位置这三个问题想清楚代码基本上不会出大错。另外二分查找一定要配合“小数据模拟 随机对拍”来练只看不写是没有效果的。打卡第三天把二分法和这些变体过完我对二分查找的掌握比前两天明显更扎实。下一步我打算把双指针和滑动窗口也按同样的方式整理一遍到时候再分享实测经验。