很多人刷题的第一步就是二分查找但真正敢说自己写对二分的人比想象中少得多。LeetCode 704这道题看似简单到只有十几行代码实际上一旦让你改一个条件、换一种写法很多老手也会翻车。今天我就把这道题从头到尾拆开讲从两种区间模板到底层原理再到各种变种题的应对套路一次讲透。1. 先搞清楚二分查找到底在解决什么问题1.1 从生活场景理解每次排除一半想象你在一个从1到100的整数里猜数字对方告诉你大了还是小了。最高效的策略一定不是从1开始一个一个试而是先猜50——如果对方说大了答案一定在1到49之间你直接排除了50个数字继续说小再往下折半。最多7次你就能锁定答案这就是二分查找。这个思维模型对应到数组里就是在一个有序数组中找一个目标值每次比较中间元素根据大小关系决定丢弃左半部分还是右半部分。704题就是这么个场景给你一个升序排列的整数数组nums和一个目标值target返回target在数组中的下标不存在就返回-1。但我要说的是这个生活化理解只是入门。真正写代码的时候大家面临的坑往往不在有没有理解折半而在边界条件怎么处理。明明逻辑看起来是对的一跑就死循环、一跑就数组越界原因就是你没有抓住二分查找背后的循环不变量。1.2 二分查找的适用前提有序只是表面单调性才是本质很多人以为数组必须有序才能用二分这个说法太狭隘了。准确地说二分查找适用的前提是能够根据某个条件把数组分成左右两个部分并且能明确判断答案在哪一侧。有序数组满足这个特性因为它天然具有单调性中间值小于target那target一定在右半边中间值大于target那target一定在左半边。换句话说你不需要数组严格有序只要数组具备二段性就可以二分。比如旋转排序数组中的最小值这道题数组本身就是两段有序拼接的你依然可以根据中间值与右端点的关系判断最小值落在哪一侧。再比如找出第一个大于等于x的位置同样可以用二分去找。用一句话总结二分的本质不是有序而是单调不是查找而是排除。每一次比较之后你都必须能丢掉至少一半的候选区间。2. 704题完整拆解两种区间模板的差别2.1 左闭右闭模板最容易上手的第一选择先看最经典的左闭右闭写法。所谓左闭右闭就是每次搜索的区间是[left, right]左右两个端点都包含在搜索范围内。初始时left 0right len(nums) - 1。def search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1这里的循环条件是left right因为当left right的时候区间里还有一个元素这个元素还没有被检查过必须进入循环。当nums[mid] target时说明mid这个位置的值比目标小而且数组是升序的那么mid以及mid左边的所有位置都不可能等于target所以下一次搜索区间变成[mid 1, right]即left mid 1。反过来当nums[mid] target时说明mid以及mid右边都不可能区间变成[left, mid - 1]即right mid - 1。这个模板的核心就是每次比较完都把边界移动到mid的两侧确保闭区间里剩下的都是还没排除的候选元素。写的时候必须搞清楚一件事这个区间里的每一个下标到底代表还没检验过的数还是已经排除掉的数。在左闭右闭的写法里区间内的每个数都没有被排除所以一旦mid不是答案就直接把这个数连同它不可能的一侧一起丢出去。2.2 左闭右开模板面试官更喜欢的严谨写法再看左闭右开写法即每次搜索的区间是[left, right)左端点包含右端点不包含。初始时left 0right len(nums)注意此时right是数组长度不是一个有效的下标。def search(nums, target): left, right 0, len(nums) # 区间 [left, right) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1这个写法的循环条件是left right当left right时区间为空说明已经找不到目标值了。重点在else分支当nums[mid] target时区间应该收缩到[left, mid)所以right mid而不是right mid - 1。因为你定义的是开区间mid本身不在区间内但mid左侧的数都在直接让right mid表示新的搜索范围是mid左边。左闭右开的好处是区间定义非常干净[left, right)天然表示待搜索区间是left到right-1配合while left right整个循环过程严格不越界也不需要额外处理left right时是否要检查元素的问题。坏处是第一次接触的人容易在right mid还是right mid - 1这里懵。2.3 两种模板的核心区别与选型建议我把两种模板的关键差异整理成一张表你对照着看就很清楚了。对比维度左闭右闭 [left, right]左闭右开 [left, right)初始 rightlen(nums) - 1len(nums)循环条件left rightleft rightmid 归属区间内区间内nums[mid] targetleft mid 1left mid 1nums[mid] targetright mid - 1right mid区间空的条件left rightleft right选哪个模板其实都可以我个人的建议是固定一个用熟不要每次刷题都换。如果你刚开始接触二分推荐从左闭右闭入手逻辑直接、和直觉贴合等到写变种题、做寻找左边界这类问题时左闭右开往往更省心因为不会出现right mid - 1之后导致边界错乱的情况。还有一点很关键不管你选哪个模板mid的计算都建议写成left (right - left) // 2而不是(left right) // 2。前者能有效避免在left和right都很大的时候整数溢出虽然704这种题目根本不会溢出但好习惯要从第一道题养成。3. 实操过程从暴力到二分的实现细节3.1 暴力解法与时间复杂度对比先说暴力解法直接遍历整个数组一个一个比过去def search(nums, target): for i in range(len(nums)): if nums[i] target: return i return -1这个写法在数组很短的时候完全没问题也能通过LeetCode的测试。但它的时间复杂度是O(n)意味着数组长度翻倍最坏情况下的比较次数也翻倍。而二分查找每次比较都排除掉一半的数据时间复杂度只有O(log n)。这里我说一个很多人忽略的点O(log n)到底快了多少假设数组长度是10亿暴力查找最坏比较10亿次而二分查找最多比较30次——因为2的30次方约等于10.7亿。这就是二分查找作为基础算法的恐怖之处。它不依赖任何魔法纯粹靠每次排除一半这个思想。当然二分查找的前提是数据已经有序。如果你每次查找前都要先排序那排序的O(n log n)成本反而可能拖垮整体性能。实际工程里一般有两种做法一是数据在写入时就维护有序二是先批量排序再反复查询。704题直接给你有序数组省去了这层考虑所以它的核心考点就是把折半写对。3.2 完整代码实现Python、Java、C三个版本Python版本前面已经给了这里我补上Java和C方便不同语言背景的人直接对照。Java左闭右闭版本class Solution { public int search(int[] nums, int target) { int left 0, right nums.length - 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; } }C左闭右开版本class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size(); 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; } };三个语言写下来你可能会发现逻辑完全一致差别只是语法。二分查找最难的从来不是语言而是你能不能把区间定义说清楚并且让每一步的代码都严格符合这个定义。3.3 编码细节循环不变量与死循环预防我把这套代码背后的核心原则拆成三条你写任何二分题都用得上。第一条定义清楚你的循环不变量。比如左闭右闭版本中不变量是目标值如果存在一定在区间[left, right]中。你每一次更新left或right都必须保证这个命题依然成立。如果你写着写着让right mid在左闭右闭版本里就可能把一个还未检查的mid排除掉或者更糟——让区间不缩小直接死循环。第二条确保每次循环后区间都在缩小。因为mid在区间内所以left mid 1之后新区间一定比旧区间小至少去掉了midright mid - 1之后也同理。如果是左闭右开版本right mid同样能保证区间缩小因为mid right成立。一旦出现left mid或right mid且mid等于边界值的写法区间就可能永远不缩小。第三条循环终止后left或者right代表什么含义要心里有数。在704题里如果循环结束还没返回说明目标值不存在返回-1。但在变种题里循环结束后的left往往就是第一个大于等于target的下标这个含义在做插入位置、寻找边界类题目时特别有用。4. 常见问题与排查技巧实录4.1 死循环最常见的翻车现场很多初学者在写二分时遇到死循环最典型的情况是出现在寻找左边界这类变种题里。比如你写了一段代码当nums[mid] target时执行left mid当目标值就在右边时如果left和right相邻mid left (right - left) // 2计算出的mid恰好等于left更新left mid之后left没变化区间永远不缩小于是死循环。排查死循环的思路很简单把mid的计算过程和left、right的更新过程在纸上演算一遍。选一组只有两个元素的数组比如[1, 3]target设为2或者3手动走一遍循环。如果某一次循环结束后left和right的值和进入循环前完全一样那你一定写出了区间不缩小的问题。解决方法就一条凡是left mid的地方改成left mid 1或者把right mid改成right mid - 1具体看你的区间定义。4.2 边界条件错误差一错误从哪来差一错误off-by-one是二分查找里的另一个高发问题。典型症状是目标值在数组最左边或最右边时返回了-1或者返回了错误的下标。比如用左闭右闭模板时有人把初始right写成len(nums)循环条件写成left right那么数组最后一个元素永远进入不了搜索区间。反过来说用左闭右开模板时有人把right初始化为len(nums) - 1那么left right时区间实际上只覆盖了[left, right - 1]同样漏掉了最后一个有效元素。排查这类问题我建议你专门测几个边界用例空数组nums []单元素数组nums [5]目标值在数组开头nums [1,2,3,4,5], target 1目标值在数组末尾nums [1,2,3,4,5], target 5目标值不存在但介于数组元素之间nums [1,3,5], target 4这五个用例跑通了你的基本二分逻辑就八九不离十了。4.3 典型问题速查表我在实际写代码过程中遇到过的坑整理成一个速查表你直接收藏。现象可能原因解决方向死循环卡在while里区间没有缩小left或right更新不当检查是否出现了left mid且mid left的情况返回-1但目标明明存在数组最后一个元素没被搜到检查初始right是否正确闭区间是否漏掉了末尾返回下标比预期大1区间定位偏右right边界多算了一个位置核对闭区间/开区间的right写法mid溢出变为负数left right超出整型范围改用left (right - left) // 2数组越界访问nums[mid]mid计算出界多半是right初始值错了检查right初始化和循环条件是否一致这些问题的根源几乎都指向同一个点你没有把区间定义写下来全靠脑子脑补。我自己的习惯是写二分之前先在注释里写清楚当前区间是闭区间还是开区间然后每一行代码都对着这个定义检查一遍。看起来慢实际上现在每次都能一遍写对。5. 从704题到整个二分家族变种套路与抽象模型5.1 三个高频变种查找左边界、右边界、插入位置刷完704题你很快会遇到它的升级版本给你一个有序数组可能包含重复元素让你找出某个值第一次出现的位置、最后一次出现的位置或者找不到时返回它应该插入的位置。这些题在LeetCode里是34. 在排序数组中查找元素的第一个和最后一个位置、35. 搜索插入位置都是高频面试题。我做这些题的经验是别去背代码先建立模板思维。比如查找左边界左闭右开版本非常好用def lower_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 left这段代码的返回值left的含义是第一个不小于target的下标。如果nums[mid] target说明target只可能在mid右边所以left mid 1否则nums[mid] targetmid可能就是左边界所以不能排除mid要让right mid。对比704题你会发现唯一的变化就是把的分支合并到了里——这就是二分模板的微调思维。查找右边界则相反可以这么写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 left - 1返回值left是第一个大于target的下标减1就是最后一个等于target的位置。如果你想要的是最后一个小于等于target的下标这个写法依然适用。本质上二分变种题考的就是你对、、、四个条件的选择以及返回left还是left-1的微调理解了区间定义这些都是一层窗户纸的事。5.2 抽象模型把任意问题转换成单调判断如果你还想更进一步就要从查找目标值上升到二分答案的层面。很多看似和数组查找无关的问题其实都能抽象成二分。比如在正整数范围内找到满足某个条件的最大值/最小值典型的有求平方根在[0, x]里找一个数y使得y * y x搜索旋转排序数组在看似无序的数组里通过判断mid和left/right的关系仍然可以进行二分数组中的峰值虽然数组无序但左边比我大就一定有峰值在左边这个判断满足了二段性也能二分。这类题的通法是先写出判断函数check(mid)它返回布尔值或某种比较结果然后根据题目的单调性决定收缩哪一侧。704题里的nums[mid] target本质上就是一个check函数。当你把判断条件和收缩方式解耦二分就从一个只会查找的算法变成了解决最优化问题的通用工具。说到这里我个人的体会是二分查找是所有算法里代码量最少、思维含量最高的那一类。你不需要背模板真正要理解的是区间定义和单调性。我第一次刷704题的时候觉得自己一次就写对了结果半个月后重新写居然在right mid还是right mid - 1上纠结了很久。后来把闭区间/开区间这个不变量刻在脑子里所有二分题基本都是一遍过。最后再分享一个小技巧如果你实在不确定自己的二分代码有没有写好拿一组数组长度为2的数据在纸上跑一遍比如[1, 3]找3找2找1。因为长度2正好是left和right相邻的临界场景90%的边界错误都能在这里暴露出来。对着表格逐行更新变量比自己盯着屏幕干想效率高太多了。
二分查找边界与循环不变量：从LeetCode 704到变种题全解
很多人刷题的第一步就是二分查找但真正敢说自己写对二分的人比想象中少得多。LeetCode 704这道题看似简单到只有十几行代码实际上一旦让你改一个条件、换一种写法很多老手也会翻车。今天我就把这道题从头到尾拆开讲从两种区间模板到底层原理再到各种变种题的应对套路一次讲透。1. 先搞清楚二分查找到底在解决什么问题1.1 从生活场景理解每次排除一半想象你在一个从1到100的整数里猜数字对方告诉你大了还是小了。最高效的策略一定不是从1开始一个一个试而是先猜50——如果对方说大了答案一定在1到49之间你直接排除了50个数字继续说小再往下折半。最多7次你就能锁定答案这就是二分查找。这个思维模型对应到数组里就是在一个有序数组中找一个目标值每次比较中间元素根据大小关系决定丢弃左半部分还是右半部分。704题就是这么个场景给你一个升序排列的整数数组nums和一个目标值target返回target在数组中的下标不存在就返回-1。但我要说的是这个生活化理解只是入门。真正写代码的时候大家面临的坑往往不在有没有理解折半而在边界条件怎么处理。明明逻辑看起来是对的一跑就死循环、一跑就数组越界原因就是你没有抓住二分查找背后的循环不变量。1.2 二分查找的适用前提有序只是表面单调性才是本质很多人以为数组必须有序才能用二分这个说法太狭隘了。准确地说二分查找适用的前提是能够根据某个条件把数组分成左右两个部分并且能明确判断答案在哪一侧。有序数组满足这个特性因为它天然具有单调性中间值小于target那target一定在右半边中间值大于target那target一定在左半边。换句话说你不需要数组严格有序只要数组具备二段性就可以二分。比如旋转排序数组中的最小值这道题数组本身就是两段有序拼接的你依然可以根据中间值与右端点的关系判断最小值落在哪一侧。再比如找出第一个大于等于x的位置同样可以用二分去找。用一句话总结二分的本质不是有序而是单调不是查找而是排除。每一次比较之后你都必须能丢掉至少一半的候选区间。2. 704题完整拆解两种区间模板的差别2.1 左闭右闭模板最容易上手的第一选择先看最经典的左闭右闭写法。所谓左闭右闭就是每次搜索的区间是[left, right]左右两个端点都包含在搜索范围内。初始时left 0right len(nums) - 1。def search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1这里的循环条件是left right因为当left right的时候区间里还有一个元素这个元素还没有被检查过必须进入循环。当nums[mid] target时说明mid这个位置的值比目标小而且数组是升序的那么mid以及mid左边的所有位置都不可能等于target所以下一次搜索区间变成[mid 1, right]即left mid 1。反过来当nums[mid] target时说明mid以及mid右边都不可能区间变成[left, mid - 1]即right mid - 1。这个模板的核心就是每次比较完都把边界移动到mid的两侧确保闭区间里剩下的都是还没排除的候选元素。写的时候必须搞清楚一件事这个区间里的每一个下标到底代表还没检验过的数还是已经排除掉的数。在左闭右闭的写法里区间内的每个数都没有被排除所以一旦mid不是答案就直接把这个数连同它不可能的一侧一起丢出去。2.2 左闭右开模板面试官更喜欢的严谨写法再看左闭右开写法即每次搜索的区间是[left, right)左端点包含右端点不包含。初始时left 0right len(nums)注意此时right是数组长度不是一个有效的下标。def search(nums, target): left, right 0, len(nums) # 区间 [left, right) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1这个写法的循环条件是left right当left right时区间为空说明已经找不到目标值了。重点在else分支当nums[mid] target时区间应该收缩到[left, mid)所以right mid而不是right mid - 1。因为你定义的是开区间mid本身不在区间内但mid左侧的数都在直接让right mid表示新的搜索范围是mid左边。左闭右开的好处是区间定义非常干净[left, right)天然表示待搜索区间是left到right-1配合while left right整个循环过程严格不越界也不需要额外处理left right时是否要检查元素的问题。坏处是第一次接触的人容易在right mid还是right mid - 1这里懵。2.3 两种模板的核心区别与选型建议我把两种模板的关键差异整理成一张表你对照着看就很清楚了。对比维度左闭右闭 [left, right]左闭右开 [left, right)初始 rightlen(nums) - 1len(nums)循环条件left rightleft rightmid 归属区间内区间内nums[mid] targetleft mid 1left mid 1nums[mid] targetright mid - 1right mid区间空的条件left rightleft right选哪个模板其实都可以我个人的建议是固定一个用熟不要每次刷题都换。如果你刚开始接触二分推荐从左闭右闭入手逻辑直接、和直觉贴合等到写变种题、做寻找左边界这类问题时左闭右开往往更省心因为不会出现right mid - 1之后导致边界错乱的情况。还有一点很关键不管你选哪个模板mid的计算都建议写成left (right - left) // 2而不是(left right) // 2。前者能有效避免在left和right都很大的时候整数溢出虽然704这种题目根本不会溢出但好习惯要从第一道题养成。3. 实操过程从暴力到二分的实现细节3.1 暴力解法与时间复杂度对比先说暴力解法直接遍历整个数组一个一个比过去def search(nums, target): for i in range(len(nums)): if nums[i] target: return i return -1这个写法在数组很短的时候完全没问题也能通过LeetCode的测试。但它的时间复杂度是O(n)意味着数组长度翻倍最坏情况下的比较次数也翻倍。而二分查找每次比较都排除掉一半的数据时间复杂度只有O(log n)。这里我说一个很多人忽略的点O(log n)到底快了多少假设数组长度是10亿暴力查找最坏比较10亿次而二分查找最多比较30次——因为2的30次方约等于10.7亿。这就是二分查找作为基础算法的恐怖之处。它不依赖任何魔法纯粹靠每次排除一半这个思想。当然二分查找的前提是数据已经有序。如果你每次查找前都要先排序那排序的O(n log n)成本反而可能拖垮整体性能。实际工程里一般有两种做法一是数据在写入时就维护有序二是先批量排序再反复查询。704题直接给你有序数组省去了这层考虑所以它的核心考点就是把折半写对。3.2 完整代码实现Python、Java、C三个版本Python版本前面已经给了这里我补上Java和C方便不同语言背景的人直接对照。Java左闭右闭版本class Solution { public int search(int[] nums, int target) { int left 0, right nums.length - 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; } }C左闭右开版本class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size(); 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; } };三个语言写下来你可能会发现逻辑完全一致差别只是语法。二分查找最难的从来不是语言而是你能不能把区间定义说清楚并且让每一步的代码都严格符合这个定义。3.3 编码细节循环不变量与死循环预防我把这套代码背后的核心原则拆成三条你写任何二分题都用得上。第一条定义清楚你的循环不变量。比如左闭右闭版本中不变量是目标值如果存在一定在区间[left, right]中。你每一次更新left或right都必须保证这个命题依然成立。如果你写着写着让right mid在左闭右闭版本里就可能把一个还未检查的mid排除掉或者更糟——让区间不缩小直接死循环。第二条确保每次循环后区间都在缩小。因为mid在区间内所以left mid 1之后新区间一定比旧区间小至少去掉了midright mid - 1之后也同理。如果是左闭右开版本right mid同样能保证区间缩小因为mid right成立。一旦出现left mid或right mid且mid等于边界值的写法区间就可能永远不缩小。第三条循环终止后left或者right代表什么含义要心里有数。在704题里如果循环结束还没返回说明目标值不存在返回-1。但在变种题里循环结束后的left往往就是第一个大于等于target的下标这个含义在做插入位置、寻找边界类题目时特别有用。4. 常见问题与排查技巧实录4.1 死循环最常见的翻车现场很多初学者在写二分时遇到死循环最典型的情况是出现在寻找左边界这类变种题里。比如你写了一段代码当nums[mid] target时执行left mid当目标值就在右边时如果left和right相邻mid left (right - left) // 2计算出的mid恰好等于left更新left mid之后left没变化区间永远不缩小于是死循环。排查死循环的思路很简单把mid的计算过程和left、right的更新过程在纸上演算一遍。选一组只有两个元素的数组比如[1, 3]target设为2或者3手动走一遍循环。如果某一次循环结束后left和right的值和进入循环前完全一样那你一定写出了区间不缩小的问题。解决方法就一条凡是left mid的地方改成left mid 1或者把right mid改成right mid - 1具体看你的区间定义。4.2 边界条件错误差一错误从哪来差一错误off-by-one是二分查找里的另一个高发问题。典型症状是目标值在数组最左边或最右边时返回了-1或者返回了错误的下标。比如用左闭右闭模板时有人把初始right写成len(nums)循环条件写成left right那么数组最后一个元素永远进入不了搜索区间。反过来说用左闭右开模板时有人把right初始化为len(nums) - 1那么left right时区间实际上只覆盖了[left, right - 1]同样漏掉了最后一个有效元素。排查这类问题我建议你专门测几个边界用例空数组nums []单元素数组nums [5]目标值在数组开头nums [1,2,3,4,5], target 1目标值在数组末尾nums [1,2,3,4,5], target 5目标值不存在但介于数组元素之间nums [1,3,5], target 4这五个用例跑通了你的基本二分逻辑就八九不离十了。4.3 典型问题速查表我在实际写代码过程中遇到过的坑整理成一个速查表你直接收藏。现象可能原因解决方向死循环卡在while里区间没有缩小left或right更新不当检查是否出现了left mid且mid left的情况返回-1但目标明明存在数组最后一个元素没被搜到检查初始right是否正确闭区间是否漏掉了末尾返回下标比预期大1区间定位偏右right边界多算了一个位置核对闭区间/开区间的right写法mid溢出变为负数left right超出整型范围改用left (right - left) // 2数组越界访问nums[mid]mid计算出界多半是right初始值错了检查right初始化和循环条件是否一致这些问题的根源几乎都指向同一个点你没有把区间定义写下来全靠脑子脑补。我自己的习惯是写二分之前先在注释里写清楚当前区间是闭区间还是开区间然后每一行代码都对着这个定义检查一遍。看起来慢实际上现在每次都能一遍写对。5. 从704题到整个二分家族变种套路与抽象模型5.1 三个高频变种查找左边界、右边界、插入位置刷完704题你很快会遇到它的升级版本给你一个有序数组可能包含重复元素让你找出某个值第一次出现的位置、最后一次出现的位置或者找不到时返回它应该插入的位置。这些题在LeetCode里是34. 在排序数组中查找元素的第一个和最后一个位置、35. 搜索插入位置都是高频面试题。我做这些题的经验是别去背代码先建立模板思维。比如查找左边界左闭右开版本非常好用def lower_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 left这段代码的返回值left的含义是第一个不小于target的下标。如果nums[mid] target说明target只可能在mid右边所以left mid 1否则nums[mid] targetmid可能就是左边界所以不能排除mid要让right mid。对比704题你会发现唯一的变化就是把的分支合并到了里——这就是二分模板的微调思维。查找右边界则相反可以这么写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 left - 1返回值left是第一个大于target的下标减1就是最后一个等于target的位置。如果你想要的是最后一个小于等于target的下标这个写法依然适用。本质上二分变种题考的就是你对、、、四个条件的选择以及返回left还是left-1的微调理解了区间定义这些都是一层窗户纸的事。5.2 抽象模型把任意问题转换成单调判断如果你还想更进一步就要从查找目标值上升到二分答案的层面。很多看似和数组查找无关的问题其实都能抽象成二分。比如在正整数范围内找到满足某个条件的最大值/最小值典型的有求平方根在[0, x]里找一个数y使得y * y x搜索旋转排序数组在看似无序的数组里通过判断mid和left/right的关系仍然可以进行二分数组中的峰值虽然数组无序但左边比我大就一定有峰值在左边这个判断满足了二段性也能二分。这类题的通法是先写出判断函数check(mid)它返回布尔值或某种比较结果然后根据题目的单调性决定收缩哪一侧。704题里的nums[mid] target本质上就是一个check函数。当你把判断条件和收缩方式解耦二分就从一个只会查找的算法变成了解决最优化问题的通用工具。说到这里我个人的体会是二分查找是所有算法里代码量最少、思维含量最高的那一类。你不需要背模板真正要理解的是区间定义和单调性。我第一次刷704题的时候觉得自己一次就写对了结果半个月后重新写居然在right mid还是right mid - 1上纠结了很久。后来把闭区间/开区间这个不变量刻在脑子里所有二分题基本都是一遍过。最后再分享一个小技巧如果你实在不确定自己的二分代码有没有写好拿一组数组长度为2的数据在纸上跑一遍比如[1, 3]找3找2找1。因为长度2正好是left和right相邻的临界场景90%的边界错误都能在这里暴露出来。对着表格逐行更新变量比自己盯着屏幕干想效率高太多了。
