1. 二分算法到底快在哪先把问题想清楚再写代码刚入行的头两年我对二分算法的态度是能用就行。直到有一次线上排查一个库存扣减的接口数据量到了百万级遍历查找直接把响应时间拖到了秒级我才痛下决心把这个算法从头到尾捋了一遍。捋完之后发现二分这东西看着简单真正写对、写稳、写到能扛住边界的人其实不多。这篇就来聊聊我理解的二分算法尽量做到一学就懂、一写就会。先说说二分算法是什么。它的学名是二分查找也有人叫折半查找核心思路非常朴素在一个有序的序列里每次取中间位置的元素跟目标值比较根据比较结果把搜索范围砍掉一半如此反复直到找到目标或者范围为空。它解决的问题就是在一个有序集合里快速定位某个值适用场景包括有序数组查找、答案区间逼近、单调函数求根、资源分配的最优解搜索等等。它适合谁看我的判断是三类人一是刚开始学数据结构与算法、被各种边界条件折磨的新手二是刷题时能默写模板但一改就错的进阶者三是工作里需要处理大规模有序数据、想写出工业级稳定代码的工程师。三类人的痛点不一样但底层对二分的理解是共通的——区间怎么定义、循环什么时候停、边界怎么收缩这三件事想透了二分就不再是玄学。我个人的经验是二分算法的门槛不在看懂而在写对。你可能五分钟就能理解它的思想但很可能在接下来半年里反复因为mid取整方向、left和right的更新方式、循环终止条件而写出死循环或者漏解。所以这篇的重点会放在为什么这样写而不是单纯给你一个模板让你背。2. 从猜数字游戏理解二分思想其实一点不复杂2.1 一个生活场景把二分讲透我特别喜欢用猜数字游戏来解释二分。规则很简单我心里想一个 1 到 100 之间的整数你来猜我每次只告诉你大了小了或者猜对了。最笨的办法是从 1 开始一个一个猜运气差要猜 100 次。稍微聪明一点的人会先猜 50如果我说大了那答案一定在 1 到 49 之间刚才那一半直接被排除掉了接着猜 25再排除一半。最多 7 次就能锁定答案。这就是二分的全部精髓利用有序性这里是大小关系每次排除掉一半的候选区间。从 100 个候选到 1 个候选每次除以 2需要多少次log₂100 ≈ 6.64向上取整就是 7 次。这个数字不是巧合它就是二分算法的时间复杂度O(log n)的直观来源。把这个游戏翻译成代码语言候选区间就是数组的下标范围[left, right]每次猜的中间位置就是mid我的回答大了小了就对应着把right往左收或者把left往右收。你看算法思想本身没有任何高深的地方难点全在把区间这个概念在代码里表示准确。2.2 为什么必须是有序的单调性是二分的命根子很多人知道二分要求有序但没想过为什么。道理在于二分每次排除一半依赖的是一个确定的推断如果中间值比目标大那么比中间值更大的那一半一定都不可能是答案。这个推断成立的前提就是序列必须有序更准确地说是具备某种单调性。如果数组是无序的[3, 1, 4, 1, 5, 9, 2, 6]你取中间值 1发现它比目标 6 小你能说右边都大于 6吗不能右边还有 5、9、2 这些乱七八糟的值。推断不成立排除一半就是错的算法直接失效。这里我要补充一个进阶认知二分真正要求的不是数组有序而是你用来做判断的那个性质具有单调性。这是什么意思举个例子我们要在一个先递增后递减的数组里找峰值这个数组整体不有序但峰值左边单调递增、右边单调递减这个性质是单调的照样可以用二分。后面讲二分答案的时候你会更深刻地体会到这一点——很多题目里我们二分的对象根本不是数组而是一个抽象的答案区间。2.3 时间复杂度是怎么算出来的面试里经常被问二分的时间复杂度是多少怎么推导的很多人张口就是O(log n)但说不清推导过程。其实很简单。设数组长度为n第一次查找后剩余n/2第二次剩余n/4第k次剩余n / 2^k。当剩余元素个数降到 1 时结束也就是n / 2^k 1解得k log₂n。所以循环最多执行log₂n次每次循环内部只做了常数次比较和赋值总时间复杂度就是O(log n)。这个量级有多恐怖n 10^9十亿的时候log₂n ≈ 30。也就是说在十亿个有序数据里找一个数二分最多只要 30 次比较。而线性遍历最坏要十亿次。这就是为什么在海量有序数据场景下二分是无可替代的。我前面提到的库存扣减那个案例正是把线性查找换成了基于有序索引的二分定位响应时间从秒级降到了毫秒级。注意二分的时间复杂度优势建立在数据已经有序这个前提上。如果为了二分专门去排序那么排序本身的O(n log n)开销往往比一次线性查找还大。所以要不要用二分这件事得结合实际场景判断不是无脑上。3. 两种经典写法左闭右闭与左闭右开3.1 左闭右闭写法最符合直觉的一种区间表示法是二分最容易让人混乱的地方。所谓的左闭右闭指的是搜索区间用[left, right]表示左右两端的下标都是有效的、都在候选范围内。写成代码长这样def binary_search(nums, target): left, right 0, len(nums) - 1 # 区间 [left, right] while left right: # 区间非空时继续 mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # 目标在右半区mid 已排除 else: right mid - 1 # 目标在左半区mid 已排除 return -1这段代码里有三个关键点我逐一解释为什么这么写。第一right初始化为len(nums) - 1因为区间是闭的最后一个元素的下标就是len(nums) - 1。第二循环条件是left right因为当left right时区间里还有一个元素[left, left]还没查完必须继续。第三更新边界时是left mid 1和right mid - 1因为mid位置已经比较过了、可以确定不是答案所以要排除掉不能写成left mid。3.2 左闭右开写法工业代码里更常见左闭右开用[left, right)表示区间左端有效、右端无效。这种表示法在很多标准库比如 C 的迭代器区间里是主流代码长这样def binary_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 # 注意这里是 mid 而不是 mid-1 return -1对比一下就能发现区别right初始化为len(nums)因为右端取不到循环条件是left right因为当left right时区间[left, left)已经是空的了最关键的是right更新时写的是right mid而不是right mid - 1因为mid本身就是开区间的边界、本来就不在候选范围里。我个人的体会是左闭右开在推导含重复元素的边界问题时会少很多心智负担因为开区间端点天然被排除这个语义和right mid的写法是自洽的。所以我给新手的建议是先死磕左闭右闭把逻辑理通然后长期使用左闭右开来写生产代码。3.3 两种写法怎么选一张表说清楚对比项左闭右闭[l, r]左闭右开[l, r)right 初值len(nums) - 1len(nums)循环条件left rightleft rightright 更新right mid - 1right mid区间空判定left rightleft right直觉友好度高中边界题稳定性中高选哪个都行关键是选定一种之后整道题、整个项目里保持一致。最怕的就是一会儿左闭右闭、一会儿左闭右开然后mid - 1、mid 1随手乱写不死循环才怪。我在 code review 里见过太多因为混用两种风格而写出的 bug这类问题往往隐蔽性极强、只在特定数据量下触发。
二分查找到底快在哪：从猜数字到边界写法一次讲透
1. 二分算法到底快在哪先把问题想清楚再写代码刚入行的头两年我对二分算法的态度是能用就行。直到有一次线上排查一个库存扣减的接口数据量到了百万级遍历查找直接把响应时间拖到了秒级我才痛下决心把这个算法从头到尾捋了一遍。捋完之后发现二分这东西看着简单真正写对、写稳、写到能扛住边界的人其实不多。这篇就来聊聊我理解的二分算法尽量做到一学就懂、一写就会。先说说二分算法是什么。它的学名是二分查找也有人叫折半查找核心思路非常朴素在一个有序的序列里每次取中间位置的元素跟目标值比较根据比较结果把搜索范围砍掉一半如此反复直到找到目标或者范围为空。它解决的问题就是在一个有序集合里快速定位某个值适用场景包括有序数组查找、答案区间逼近、单调函数求根、资源分配的最优解搜索等等。它适合谁看我的判断是三类人一是刚开始学数据结构与算法、被各种边界条件折磨的新手二是刷题时能默写模板但一改就错的进阶者三是工作里需要处理大规模有序数据、想写出工业级稳定代码的工程师。三类人的痛点不一样但底层对二分的理解是共通的——区间怎么定义、循环什么时候停、边界怎么收缩这三件事想透了二分就不再是玄学。我个人的经验是二分算法的门槛不在看懂而在写对。你可能五分钟就能理解它的思想但很可能在接下来半年里反复因为mid取整方向、left和right的更新方式、循环终止条件而写出死循环或者漏解。所以这篇的重点会放在为什么这样写而不是单纯给你一个模板让你背。2. 从猜数字游戏理解二分思想其实一点不复杂2.1 一个生活场景把二分讲透我特别喜欢用猜数字游戏来解释二分。规则很简单我心里想一个 1 到 100 之间的整数你来猜我每次只告诉你大了小了或者猜对了。最笨的办法是从 1 开始一个一个猜运气差要猜 100 次。稍微聪明一点的人会先猜 50如果我说大了那答案一定在 1 到 49 之间刚才那一半直接被排除掉了接着猜 25再排除一半。最多 7 次就能锁定答案。这就是二分的全部精髓利用有序性这里是大小关系每次排除掉一半的候选区间。从 100 个候选到 1 个候选每次除以 2需要多少次log₂100 ≈ 6.64向上取整就是 7 次。这个数字不是巧合它就是二分算法的时间复杂度O(log n)的直观来源。把这个游戏翻译成代码语言候选区间就是数组的下标范围[left, right]每次猜的中间位置就是mid我的回答大了小了就对应着把right往左收或者把left往右收。你看算法思想本身没有任何高深的地方难点全在把区间这个概念在代码里表示准确。2.2 为什么必须是有序的单调性是二分的命根子很多人知道二分要求有序但没想过为什么。道理在于二分每次排除一半依赖的是一个确定的推断如果中间值比目标大那么比中间值更大的那一半一定都不可能是答案。这个推断成立的前提就是序列必须有序更准确地说是具备某种单调性。如果数组是无序的[3, 1, 4, 1, 5, 9, 2, 6]你取中间值 1发现它比目标 6 小你能说右边都大于 6吗不能右边还有 5、9、2 这些乱七八糟的值。推断不成立排除一半就是错的算法直接失效。这里我要补充一个进阶认知二分真正要求的不是数组有序而是你用来做判断的那个性质具有单调性。这是什么意思举个例子我们要在一个先递增后递减的数组里找峰值这个数组整体不有序但峰值左边单调递增、右边单调递减这个性质是单调的照样可以用二分。后面讲二分答案的时候你会更深刻地体会到这一点——很多题目里我们二分的对象根本不是数组而是一个抽象的答案区间。2.3 时间复杂度是怎么算出来的面试里经常被问二分的时间复杂度是多少怎么推导的很多人张口就是O(log n)但说不清推导过程。其实很简单。设数组长度为n第一次查找后剩余n/2第二次剩余n/4第k次剩余n / 2^k。当剩余元素个数降到 1 时结束也就是n / 2^k 1解得k log₂n。所以循环最多执行log₂n次每次循环内部只做了常数次比较和赋值总时间复杂度就是O(log n)。这个量级有多恐怖n 10^9十亿的时候log₂n ≈ 30。也就是说在十亿个有序数据里找一个数二分最多只要 30 次比较。而线性遍历最坏要十亿次。这就是为什么在海量有序数据场景下二分是无可替代的。我前面提到的库存扣减那个案例正是把线性查找换成了基于有序索引的二分定位响应时间从秒级降到了毫秒级。注意二分的时间复杂度优势建立在数据已经有序这个前提上。如果为了二分专门去排序那么排序本身的O(n log n)开销往往比一次线性查找还大。所以要不要用二分这件事得结合实际场景判断不是无脑上。3. 两种经典写法左闭右闭与左闭右开3.1 左闭右闭写法最符合直觉的一种区间表示法是二分最容易让人混乱的地方。所谓的左闭右闭指的是搜索区间用[left, right]表示左右两端的下标都是有效的、都在候选范围内。写成代码长这样def binary_search(nums, target): left, right 0, len(nums) - 1 # 区间 [left, right] while left right: # 区间非空时继续 mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # 目标在右半区mid 已排除 else: right mid - 1 # 目标在左半区mid 已排除 return -1这段代码里有三个关键点我逐一解释为什么这么写。第一right初始化为len(nums) - 1因为区间是闭的最后一个元素的下标就是len(nums) - 1。第二循环条件是left right因为当left right时区间里还有一个元素[left, left]还没查完必须继续。第三更新边界时是left mid 1和right mid - 1因为mid位置已经比较过了、可以确定不是答案所以要排除掉不能写成left mid。3.2 左闭右开写法工业代码里更常见左闭右开用[left, right)表示区间左端有效、右端无效。这种表示法在很多标准库比如 C 的迭代器区间里是主流代码长这样def binary_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 # 注意这里是 mid 而不是 mid-1 return -1对比一下就能发现区别right初始化为len(nums)因为右端取不到循环条件是left right因为当left right时区间[left, left)已经是空的了最关键的是right更新时写的是right mid而不是right mid - 1因为mid本身就是开区间的边界、本来就不在候选范围里。我个人的体会是左闭右开在推导含重复元素的边界问题时会少很多心智负担因为开区间端点天然被排除这个语义和right mid的写法是自洽的。所以我给新手的建议是先死磕左闭右闭把逻辑理通然后长期使用左闭右开来写生产代码。3.3 两种写法怎么选一张表说清楚对比项左闭右闭[l, r]左闭右开[l, r)right 初值len(nums) - 1len(nums)循环条件left rightleft rightright 更新right mid - 1right mid区间空判定left rightleft right直觉友好度高中边界题稳定性中高选哪个都行关键是选定一种之后整道题、整个项目里保持一致。最怕的就是一会儿左闭右闭、一会儿左闭右开然后mid - 1、mid 1随手乱写不死循环才怪。我在 code review 里见过太多因为混用两种风格而写出的 bug这类问题往往隐蔽性极强、只在特定数据量下触发。
