提起“找数”这两个字刷过题的人应该都不陌生。无论是面试手撕代码还是竞赛里卡时间你大概率都撞见过这种题在一个数组里找出某个目标值的位置或者在某个范围内找到一个满足条件的数字。它看起来就是“循环一下比一比返回下标”简单到不能再简单可偏偏从二分查找、三分查找到哈希表、双指针、分块索引再到各种变种题算法世界里最经典的那批思路几乎都能从“找数”这个动作里长出来。我后来复盘过很多次才意识到找数题根本不是一道小题它几乎是整个数据结构与算法训练体系的微缩样本。这篇文章我会从“为什么经典”讲起把二分查找这类找数方案的原理、代码模板、边界细节、高频变体以及实战中的坑按我自己写题和分析源码时的思路完整拆一遍。想稳稳吃透排序、搜索、动态规划之前先在找数题上把“搜索空间”这个概念掰开揉碎非常值得。尤其是准备算法岗面试、刷 LeetCode、或者想从头建立算法直觉的朋友这篇应该能帮你省掉不少自己踩坑的时间。1. 为什么一道找数题能成为算法世界的常青树找数题表面上是“查一个值”实际上每一次查找都在回答同一个问题搜索空间里能否根据已有信息排除掉一部分永远不需要再看的区域。谁能在最短时间内排除最多的区域谁就拥有更优的算法。这样一想找数题就远远不止“写个循环”那么简单了它是学习算法复杂度思维的最佳起点。1.1 找数一个“麻雀虽小五脏俱全”的思维样本你随便翻开一本算法书动态规划、贪心、回溯、分治这些听上去高深的概念落到一道找数题上往往立刻变得具体。比如二分查找就是最典型的分治思想——每次比较之后把问题规模砍半剩下的部分跟原始问题结构相同继续相同的处理。这本质上就是把“大问题拆成小问题小问题和原问题同构”这个核心思想压缩在一个几行的循环里。而且找数题特别适合用来观察复杂度。暴力解法是 O(n)二分是 O(log n)哈希是 O(1)。同样一个需求仅仅因为数据和前置条件不同复杂度能差出几个量级。我见过很多刚开始学算法的人背了一堆复杂公式却不知道这些复杂度在真实题目里长什么样子。找数题能把这些复杂度全部具象化让“为什么需要好算法”这件事变得特别直观——你找一个数可能只需要几十毫秒但放到十亿条数据里O(n) 和 O(log n) 就不再是理论差距了而是“秒出”和“可能要等半天”的差距。它还是极少数能同时考察“代码功底”和“思维严密性”的题目类型。功能上只需要几行但边界条件、区间定义、循环不变量每一个细节都能挖出坑。面试官特别喜欢在找数题上做文章因为候选人背模板和真正理解模板一问 while 循环为什么是还是立刻就能分辨出来。1.2 从“搜索空间”这个角度看找数题的本质把找数题的思维抽象一层你会发现所有搜索类问题——包括 KMP 算法里的模式串匹配、A* 算法里的路径搜索、甚至深度学习训练时在损失函数上找一个最低点——都在做同一件事确定一个搜索空间然后用某种策略逐步缩小它。找数题恰恰是这种“缩小搜索空间”策略的最小展示单位。目标数存在于某个范围内我们根据规则每次排除一部分绝不会包含答案的区域最终把范围收敛到唯一目标。这个“根据规则排除区域”的动作就是算法思维里的“剪枝”也是很多高级算法的雏形。理解了找数题里的搜索空间如何被压缩后面理解回溯里的剪枝、动态规划里只保留最优子结构、博弈树里的 alpha-beta 剪枝都会轻松很多。所以我一直建议把找数题当作算法学习的第一步来练。不是因为简单而是因为它足够基础、足够常见又足够深刻。你把这个模块吃透了后面很多算法题里再遇到“找某种条件的最优位置”时都会觉得特别熟。2. 常见找数方案横评从线性扫描到二分缩小找数方案不是只有二分查找一种。不同场景、不同前提条件下最优策略完全不同。我按自己的实战经验把常用方案梳理成了四类暴力枚举、二分查找、三分查找和哈希查找。它们各有一套适用逻辑也各有各的坑。2.1 四种找数策略的适用场景对比策略前置条件时间复杂度空间复杂度典型场景核心坑点暴力枚举无O(n)O(1)数据量小、无序、无额外要求数据量大时直接超时二分查找有序或存在单调性O(log n)O(1)有序数组查找、边界搜索边界讨论复杂容易死循环三分查找单峰函数凸或凹O(log n)O(1)求极值位置要求函数严格单峰误用会错哈希查找无序即可需可哈希O(1) 平均O(n)快速判断是否存在、两数之和空间开销大哈希冲突影响性能从表里能看出一个规律前置条件越强单次查找的代价越低。这是一个非常通用的权衡——你想快就得先有结构。二分查找之所以经典是因为它只需要“有序”这一个条件就能换来 log 级别的效率性价比极高。哈希则更进一步直接放弃了对数据顺序的要求通过空间换时间在平均意义上做到 O(1) 查找。2.2 二分查找背后那个核心逻辑为什么砍半有效二分查找看起来简单但真正理解“为什么砍半有效”的人比想象中少。它依赖的底层逻辑是一个叫“单调性”的东西目标值在一侧的所有元素都小于它在另一侧的所有元素都大于它。有了这个前提你每比较一次就能确定目标不在当前那一侧进而把整个那一侧全部排除掉。我常说二分查找本质上是在做猜数字游戏。小时候玩的那种“0 到 100 里想一个数你猜我告诉你大了还是小了”的游戏就是一个最朴素的二分。你第一次猜 50如果对方说“大了”那 51 到 100 就全部不用考虑了。猜一次排除一半猜两次排除四分之三猜七次就能从 100 个数里锁定目标。到了 10 亿个数里也只需要三十次左右——因为 2 的 30 次方已经超过 10 亿在十亿级别数据里二分查找最多比较 30 次。这个“排除一半”的动作换算成数学表达就是每轮后问题规模变为原来的二分之一经过 k 轮后变为 n / 2^k当这个值缩小到 1 时停止k 就等于 log2(n)。这也是二分查找时间复杂度 O(log n) 的来由。理解了这个推导你在面试里被问“为什么是 log n”时就能直接给出这个逻辑而不是只能背结论。3. 实操过程与核心环节实现理论归理论找数题真正难的地方永远在实现。我曾经在一道“查找有序数组中第一个等于目标值的位置”上反复修改提交了五次才通过每次都是边界问题。所以这一节我把代码模板、变体操作和调试思路全部展开讲保证你看完之后能直接上手复现。3.1 先写一个不出错的经典二分查找我分享自己最常用的一套模板它是“左闭右闭”区间写法逻辑最直接也最容易验证def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1这里必须解释几个细节。第一mid left (right - left) // 2而不是(left right) // 2是为了防止 left 和 right 很大时相加溢出虽然 Python 里整数不限长度不需要操心但在 C 或 Java 里这是真实存在的隐患。第二因为区间是[left, right]两边都能取到所以循环条件是left right也就是说区间里还有一个数时也要继续查。第三每次比较后更新边界时都必须mid 1或mid - 1因为mid已经比较过了不能把它留在下一轮区间里否则可能出现死循环。这三个点理解了经典二分基本就不会出错。还有个小细节如果目标值不存在这个模板返回-1。实际工程里有些人习惯返回“第一个大于等于 target 的位置”也就是插入点。这个约定本身没有对错但必须在写代码前明确否则后续调用方容易出 bug。3.2 “找数”高频变体逐个击破面试里直接考裸二分的概率其实不高更多是考它的变形。我挑四个最高频的变体说查找左边界、查找右边界、旋转数组查找、寻找峰值。这四个吃透绝大多数二分衍生题都能覆盖。第一个变体是查找第一个等于目标值的位置。这个题的关键在于nums[mid] target时不能直接返回因为左边可能还有相等的元素。所以这个分支要改成right mid - 1把区间继续往左缩直到循环结束此时的left就是第一个目标位置。def first_equal(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: right mid - 1 else: left mid 1 return left if left len(nums) and nums[left] target else -1第二个变体是查找最后一个等于目标值的位置。思路镜像对称nums[mid] target时执行left mid 1把区间往右推最后right就是答案。这种“相同逻辑方向相反”的成对题目最适合用来检验你是否真的理解了区间收缩的本质而不是死记硬背模板。第三个变体是搜索旋转排序数组比如[4,5,6,7,0,1,2]里找 target。它的技巧是每次切出 mid 之后左右两半中必有一半是有序的。先用nums[left] nums[mid]判断左半是否有序如果有序且 target 落在左半区间就收缩 right否则去右半找。关键是理清楚“哪一半有序target 是否在有序那半的区间内”这两个判断的顺序逻辑链一旦混乱样例一跑就错。def search_rotated(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid if nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1第四个变体是寻找峰值。它打破了一个思维定式——二分不是只能用于有序数组只要“两侧数据存在某种方向性”二分同样适用。峰值题的妙处在于你不需要知道整个数组的升降结构只需要比较nums[mid]和nums[mid1]如果nums[mid] nums[mid1]说明峰值在左侧含 mid否则在右侧不含 mid。def find_peak(nums): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[mid 1]: right mid else: left mid 1 return left这个题的更新方式很特殊right mid而不是right mid - 1因为mid本身可能就是峰。同时循环条件用的是left right保证区间始终有至少两个元素能比较。一旦区间收敛到单点那个点就是峰值。这个题目特别能检验你有没有理解“什么时候该用什么时候该用”以及“边界更新到底该不该带上 mid”。3.3 不止二分三分查找与哈希表的现场决策有些找数场景并不局限于二分态度。比如求一个单峰函数的极值点二分就帮不上忙了因为单峰函数值不满足“一分为二后直接判定哪半排除”的条件但三分查找可以。它的思路是把区间三等分成m1和m2两个点比较f(m1)和f(m2)如果f(m1) f(m2)说明极值点在更右的位置于是把左边界移到m1否则右边界移到m2。这个策略在爬山问题、抛物线求最值等场景里很常见。另一种完全不同的找数场景是数据完全无序甚至只想知道“这个数在不在里面”。这种时候直接线性扫描是万不得已的方案更合适的做法是用哈希表。把每个元素的值作为 key下标作为 value 存进哈希表后续查找直接按 key 取平均 O(1)。典型题目就是“两数之和”一边遍历数组一边查哈希表里有没有target - nums[i]有就立刻返回。空间换时间的权衡在这里体现得淋漓尽致。这两类方案说明一件事找数题没有一个万能解法你真正要练的是快速识别题目里的前置条件然后挑选对应的最优策略。4. 常见问题与排查技巧实录讲完方案和代码下面这部分才是我最想写的——实际写题和面试里真正容易翻车的地方。这些坑我都真实踩过也帮别人排查过不少次。4.1 边界条件翻车现场while(l r) 还是 while(l r)这个问题几乎是二分查找的“入门第一坑”。选错了要么漏掉区间里最后一个元素导致结果错误要么在区间为空时还继续循环导致死循环或数组越界。我的建议是先选定一套模板把逻辑吃透再尝试理解另一套。左闭右闭模板[left, right]就配while left right因为当left right时区间里还有一个元素没有检查左闭右开模板[left, right)就配while left right因为当left right时区间已经为空。真正写错的人问题出在混用初始化左闭右开循环却写成或者初始化左闭右闭循环却写成。这样一组合边界行为就完全说不清了。4.2 mid 取整方向决定成败死循环的真相另一个极阴间的坑是死循环。它通常出现在使用while left right的一类模板中这个模板里不直接返回 mid而是不断收缩区间。当区间长度为 2 时mid (left right) // 2会在 Python 里向下取整也就是取靠左的那个位置。如果你在这个场景下写了left mid下一次循环如果又满足条件更新left mid区间就永远不会缩小死循环就产生了。解决办法是用left mid 1或right mid - 1来更新区间时可以放心向下取整但如果必须用left mid那就得让 mid 向上取整写成mid (left right 1) // 2。我在写“寻找最后一个等于 target 的位置”时就因为忽略了这一点卡了近半小时。这个教训值得单独拎出来说一句不要以为死循环只是退出条件写错mid 的取整方向和区间更新方式必须配套否则代码逻辑再正确也跑不出来。4.3 手撕代码时的复杂度分析怎么解释 O(log n) 才加分面试时答出二分时间复杂度是 O(log n) 只是及格线能把推导过程讲清楚才是加分项。不要只说“因为每次都砍半”更好的说法是设初始区间大小为 n每一轮比较后区间至少缩减为原来的一半经过 k 次后区间大小为 n / 2^k当区间大小缩到 1 时查找结束令 n / 2^k 1解得 k log2(n)。空间复杂度方面如果用迭代实现没有额外数组和递归栈就是 O(1)如果用递归实现递归深度为 log n空间复杂度就是 O(log n)。一个实用的表达技巧是如果面试官只问“复杂度多少”你就直接答时间和空间并给出结论如果他追问“为什么”你就把上面的推导过程说一遍。这样显得你既懂结论也懂原理。很多人只知道背结论被深入问一句就露馅非常可惜。4.4 建议按这个顺序练找数题最后给一套我验证过的练习路径。初始先闭卷手写经典二分确认模板稳定后再练“查找第一个/最后一个等于目标值”的边界变体。接下来挑战“旋转排序数组查找”因为它引入了“部分有序”的新判断维度。然后做“寻找峰值”理解二分对“方向性”而不是“严格有序”的依赖。最后回到“两数之和”对比哈希和解法和双指针解法体会不同前置条件下策略如何切换。按这个顺序练完一遍你对找数题的体系认知会比零散刷题扎实得多。5. 找数题的“算法思想溢出”从排序到深度学习如果你觉得找数题的价值止步于刷题和面试那就太小看它了。它的思维模式实际上渗透在大量高级算法里从基础排序到现代人工智能到处都能看到找数题的影子。5.1 找数思维在排序算法里的身影很多排序算法内部其实都藏着找数的动作。快速排序的 partition 过程本质上是找一个“分割点”把比它小的放到左边比它大的放到右边这个分割点选得好不好直接影响排序效率。归并排序里合并两个有序数组时每一步也是在两个区间里“找出当前最小的元素”本质上就是一次二路找最小。堆排序里反复执行的堆调整每次都要在父节点和两个孩子之间找出最大值或最小值。可以这么说排序算法之所以需要比较和交换一部分原因就是它必须反复完成“在一组候选里找出应该放在当前位置的那个元素”这个任务而这正是找数思维的核心动作。从这个角度看找数题练的不是“会写二分”这一件事而是练“如何在候选集合里快速缩小范围并做出正确选择”的通用能力。这个能力在数据结构课程里贯穿始终在二叉搜索树里查找、在跳表里跳跃查找、在 B 树里按范围查找全部都是在用不同的结构加速同一个“找数”底层操作。5.2 在搜索算法、优化算法中的身影再往上层走找数思维遍布更广阔的算法场景。图论里的最短路算法每次从待处理集合中找出距离最小的节点相当于反复“找最小值”A* 搜索里每次从开放列表中找出 f 值最小的节点是一个带启发式信息的“找最优数”回溯算法里的剪枝本质上是做题前判断“这一侧不可能有答案”从而提前排除跟二分里“这一半不可能有 target”的判断思路同源。连深度学习里的优化过程也在做找数梯度下降每步朝着损失函数下降方向移动一点本质上是在高维空间里找损失最小的那个位置。各种改进算法比如带动量的优化器、自适应学习率的优化器都是在“找最小值”这个核心任务上做搜索策略的改良。理解了找数题里“搜索空间”和“缩小范围”这两个概念再看这些现代算法你会觉得它们的骨架并不神秘。所以我个人的体会是找数题对程序员的价值不在于背会那道题本身而在于它第一次帮你建立了“搜索空间”的直觉。要知道整个算法世界大到数据库索引小到一次循环里的 boolean 检查几乎都在做同样一件事从大量可能性中快速锁定答案。想明白这一点之后再遇到任何新算法我都习惯先用“它在搜索什么空间、用什么规则缩小空间”这两个问题去拆解往往很快就能抓住本质。这套思维就是找数题送给所有算法学习者的真正礼物。
找数算法全解析：从二分查找的边界细节到变体实战与复杂度原理
提起“找数”这两个字刷过题的人应该都不陌生。无论是面试手撕代码还是竞赛里卡时间你大概率都撞见过这种题在一个数组里找出某个目标值的位置或者在某个范围内找到一个满足条件的数字。它看起来就是“循环一下比一比返回下标”简单到不能再简单可偏偏从二分查找、三分查找到哈希表、双指针、分块索引再到各种变种题算法世界里最经典的那批思路几乎都能从“找数”这个动作里长出来。我后来复盘过很多次才意识到找数题根本不是一道小题它几乎是整个数据结构与算法训练体系的微缩样本。这篇文章我会从“为什么经典”讲起把二分查找这类找数方案的原理、代码模板、边界细节、高频变体以及实战中的坑按我自己写题和分析源码时的思路完整拆一遍。想稳稳吃透排序、搜索、动态规划之前先在找数题上把“搜索空间”这个概念掰开揉碎非常值得。尤其是准备算法岗面试、刷 LeetCode、或者想从头建立算法直觉的朋友这篇应该能帮你省掉不少自己踩坑的时间。1. 为什么一道找数题能成为算法世界的常青树找数题表面上是“查一个值”实际上每一次查找都在回答同一个问题搜索空间里能否根据已有信息排除掉一部分永远不需要再看的区域。谁能在最短时间内排除最多的区域谁就拥有更优的算法。这样一想找数题就远远不止“写个循环”那么简单了它是学习算法复杂度思维的最佳起点。1.1 找数一个“麻雀虽小五脏俱全”的思维样本你随便翻开一本算法书动态规划、贪心、回溯、分治这些听上去高深的概念落到一道找数题上往往立刻变得具体。比如二分查找就是最典型的分治思想——每次比较之后把问题规模砍半剩下的部分跟原始问题结构相同继续相同的处理。这本质上就是把“大问题拆成小问题小问题和原问题同构”这个核心思想压缩在一个几行的循环里。而且找数题特别适合用来观察复杂度。暴力解法是 O(n)二分是 O(log n)哈希是 O(1)。同样一个需求仅仅因为数据和前置条件不同复杂度能差出几个量级。我见过很多刚开始学算法的人背了一堆复杂公式却不知道这些复杂度在真实题目里长什么样子。找数题能把这些复杂度全部具象化让“为什么需要好算法”这件事变得特别直观——你找一个数可能只需要几十毫秒但放到十亿条数据里O(n) 和 O(log n) 就不再是理论差距了而是“秒出”和“可能要等半天”的差距。它还是极少数能同时考察“代码功底”和“思维严密性”的题目类型。功能上只需要几行但边界条件、区间定义、循环不变量每一个细节都能挖出坑。面试官特别喜欢在找数题上做文章因为候选人背模板和真正理解模板一问 while 循环为什么是还是立刻就能分辨出来。1.2 从“搜索空间”这个角度看找数题的本质把找数题的思维抽象一层你会发现所有搜索类问题——包括 KMP 算法里的模式串匹配、A* 算法里的路径搜索、甚至深度学习训练时在损失函数上找一个最低点——都在做同一件事确定一个搜索空间然后用某种策略逐步缩小它。找数题恰恰是这种“缩小搜索空间”策略的最小展示单位。目标数存在于某个范围内我们根据规则每次排除一部分绝不会包含答案的区域最终把范围收敛到唯一目标。这个“根据规则排除区域”的动作就是算法思维里的“剪枝”也是很多高级算法的雏形。理解了找数题里的搜索空间如何被压缩后面理解回溯里的剪枝、动态规划里只保留最优子结构、博弈树里的 alpha-beta 剪枝都会轻松很多。所以我一直建议把找数题当作算法学习的第一步来练。不是因为简单而是因为它足够基础、足够常见又足够深刻。你把这个模块吃透了后面很多算法题里再遇到“找某种条件的最优位置”时都会觉得特别熟。2. 常见找数方案横评从线性扫描到二分缩小找数方案不是只有二分查找一种。不同场景、不同前提条件下最优策略完全不同。我按自己的实战经验把常用方案梳理成了四类暴力枚举、二分查找、三分查找和哈希查找。它们各有一套适用逻辑也各有各的坑。2.1 四种找数策略的适用场景对比策略前置条件时间复杂度空间复杂度典型场景核心坑点暴力枚举无O(n)O(1)数据量小、无序、无额外要求数据量大时直接超时二分查找有序或存在单调性O(log n)O(1)有序数组查找、边界搜索边界讨论复杂容易死循环三分查找单峰函数凸或凹O(log n)O(1)求极值位置要求函数严格单峰误用会错哈希查找无序即可需可哈希O(1) 平均O(n)快速判断是否存在、两数之和空间开销大哈希冲突影响性能从表里能看出一个规律前置条件越强单次查找的代价越低。这是一个非常通用的权衡——你想快就得先有结构。二分查找之所以经典是因为它只需要“有序”这一个条件就能换来 log 级别的效率性价比极高。哈希则更进一步直接放弃了对数据顺序的要求通过空间换时间在平均意义上做到 O(1) 查找。2.2 二分查找背后那个核心逻辑为什么砍半有效二分查找看起来简单但真正理解“为什么砍半有效”的人比想象中少。它依赖的底层逻辑是一个叫“单调性”的东西目标值在一侧的所有元素都小于它在另一侧的所有元素都大于它。有了这个前提你每比较一次就能确定目标不在当前那一侧进而把整个那一侧全部排除掉。我常说二分查找本质上是在做猜数字游戏。小时候玩的那种“0 到 100 里想一个数你猜我告诉你大了还是小了”的游戏就是一个最朴素的二分。你第一次猜 50如果对方说“大了”那 51 到 100 就全部不用考虑了。猜一次排除一半猜两次排除四分之三猜七次就能从 100 个数里锁定目标。到了 10 亿个数里也只需要三十次左右——因为 2 的 30 次方已经超过 10 亿在十亿级别数据里二分查找最多比较 30 次。这个“排除一半”的动作换算成数学表达就是每轮后问题规模变为原来的二分之一经过 k 轮后变为 n / 2^k当这个值缩小到 1 时停止k 就等于 log2(n)。这也是二分查找时间复杂度 O(log n) 的来由。理解了这个推导你在面试里被问“为什么是 log n”时就能直接给出这个逻辑而不是只能背结论。3. 实操过程与核心环节实现理论归理论找数题真正难的地方永远在实现。我曾经在一道“查找有序数组中第一个等于目标值的位置”上反复修改提交了五次才通过每次都是边界问题。所以这一节我把代码模板、变体操作和调试思路全部展开讲保证你看完之后能直接上手复现。3.1 先写一个不出错的经典二分查找我分享自己最常用的一套模板它是“左闭右闭”区间写法逻辑最直接也最容易验证def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1这里必须解释几个细节。第一mid left (right - left) // 2而不是(left right) // 2是为了防止 left 和 right 很大时相加溢出虽然 Python 里整数不限长度不需要操心但在 C 或 Java 里这是真实存在的隐患。第二因为区间是[left, right]两边都能取到所以循环条件是left right也就是说区间里还有一个数时也要继续查。第三每次比较后更新边界时都必须mid 1或mid - 1因为mid已经比较过了不能把它留在下一轮区间里否则可能出现死循环。这三个点理解了经典二分基本就不会出错。还有个小细节如果目标值不存在这个模板返回-1。实际工程里有些人习惯返回“第一个大于等于 target 的位置”也就是插入点。这个约定本身没有对错但必须在写代码前明确否则后续调用方容易出 bug。3.2 “找数”高频变体逐个击破面试里直接考裸二分的概率其实不高更多是考它的变形。我挑四个最高频的变体说查找左边界、查找右边界、旋转数组查找、寻找峰值。这四个吃透绝大多数二分衍生题都能覆盖。第一个变体是查找第一个等于目标值的位置。这个题的关键在于nums[mid] target时不能直接返回因为左边可能还有相等的元素。所以这个分支要改成right mid - 1把区间继续往左缩直到循环结束此时的left就是第一个目标位置。def first_equal(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: right mid - 1 else: left mid 1 return left if left len(nums) and nums[left] target else -1第二个变体是查找最后一个等于目标值的位置。思路镜像对称nums[mid] target时执行left mid 1把区间往右推最后right就是答案。这种“相同逻辑方向相反”的成对题目最适合用来检验你是否真的理解了区间收缩的本质而不是死记硬背模板。第三个变体是搜索旋转排序数组比如[4,5,6,7,0,1,2]里找 target。它的技巧是每次切出 mid 之后左右两半中必有一半是有序的。先用nums[left] nums[mid]判断左半是否有序如果有序且 target 落在左半区间就收缩 right否则去右半找。关键是理清楚“哪一半有序target 是否在有序那半的区间内”这两个判断的顺序逻辑链一旦混乱样例一跑就错。def search_rotated(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid if nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1第四个变体是寻找峰值。它打破了一个思维定式——二分不是只能用于有序数组只要“两侧数据存在某种方向性”二分同样适用。峰值题的妙处在于你不需要知道整个数组的升降结构只需要比较nums[mid]和nums[mid1]如果nums[mid] nums[mid1]说明峰值在左侧含 mid否则在右侧不含 mid。def find_peak(nums): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[mid 1]: right mid else: left mid 1 return left这个题的更新方式很特殊right mid而不是right mid - 1因为mid本身可能就是峰。同时循环条件用的是left right保证区间始终有至少两个元素能比较。一旦区间收敛到单点那个点就是峰值。这个题目特别能检验你有没有理解“什么时候该用什么时候该用”以及“边界更新到底该不该带上 mid”。3.3 不止二分三分查找与哈希表的现场决策有些找数场景并不局限于二分态度。比如求一个单峰函数的极值点二分就帮不上忙了因为单峰函数值不满足“一分为二后直接判定哪半排除”的条件但三分查找可以。它的思路是把区间三等分成m1和m2两个点比较f(m1)和f(m2)如果f(m1) f(m2)说明极值点在更右的位置于是把左边界移到m1否则右边界移到m2。这个策略在爬山问题、抛物线求最值等场景里很常见。另一种完全不同的找数场景是数据完全无序甚至只想知道“这个数在不在里面”。这种时候直接线性扫描是万不得已的方案更合适的做法是用哈希表。把每个元素的值作为 key下标作为 value 存进哈希表后续查找直接按 key 取平均 O(1)。典型题目就是“两数之和”一边遍历数组一边查哈希表里有没有target - nums[i]有就立刻返回。空间换时间的权衡在这里体现得淋漓尽致。这两类方案说明一件事找数题没有一个万能解法你真正要练的是快速识别题目里的前置条件然后挑选对应的最优策略。4. 常见问题与排查技巧实录讲完方案和代码下面这部分才是我最想写的——实际写题和面试里真正容易翻车的地方。这些坑我都真实踩过也帮别人排查过不少次。4.1 边界条件翻车现场while(l r) 还是 while(l r)这个问题几乎是二分查找的“入门第一坑”。选错了要么漏掉区间里最后一个元素导致结果错误要么在区间为空时还继续循环导致死循环或数组越界。我的建议是先选定一套模板把逻辑吃透再尝试理解另一套。左闭右闭模板[left, right]就配while left right因为当left right时区间里还有一个元素没有检查左闭右开模板[left, right)就配while left right因为当left right时区间已经为空。真正写错的人问题出在混用初始化左闭右开循环却写成或者初始化左闭右闭循环却写成。这样一组合边界行为就完全说不清了。4.2 mid 取整方向决定成败死循环的真相另一个极阴间的坑是死循环。它通常出现在使用while left right的一类模板中这个模板里不直接返回 mid而是不断收缩区间。当区间长度为 2 时mid (left right) // 2会在 Python 里向下取整也就是取靠左的那个位置。如果你在这个场景下写了left mid下一次循环如果又满足条件更新left mid区间就永远不会缩小死循环就产生了。解决办法是用left mid 1或right mid - 1来更新区间时可以放心向下取整但如果必须用left mid那就得让 mid 向上取整写成mid (left right 1) // 2。我在写“寻找最后一个等于 target 的位置”时就因为忽略了这一点卡了近半小时。这个教训值得单独拎出来说一句不要以为死循环只是退出条件写错mid 的取整方向和区间更新方式必须配套否则代码逻辑再正确也跑不出来。4.3 手撕代码时的复杂度分析怎么解释 O(log n) 才加分面试时答出二分时间复杂度是 O(log n) 只是及格线能把推导过程讲清楚才是加分项。不要只说“因为每次都砍半”更好的说法是设初始区间大小为 n每一轮比较后区间至少缩减为原来的一半经过 k 次后区间大小为 n / 2^k当区间大小缩到 1 时查找结束令 n / 2^k 1解得 k log2(n)。空间复杂度方面如果用迭代实现没有额外数组和递归栈就是 O(1)如果用递归实现递归深度为 log n空间复杂度就是 O(log n)。一个实用的表达技巧是如果面试官只问“复杂度多少”你就直接答时间和空间并给出结论如果他追问“为什么”你就把上面的推导过程说一遍。这样显得你既懂结论也懂原理。很多人只知道背结论被深入问一句就露馅非常可惜。4.4 建议按这个顺序练找数题最后给一套我验证过的练习路径。初始先闭卷手写经典二分确认模板稳定后再练“查找第一个/最后一个等于目标值”的边界变体。接下来挑战“旋转排序数组查找”因为它引入了“部分有序”的新判断维度。然后做“寻找峰值”理解二分对“方向性”而不是“严格有序”的依赖。最后回到“两数之和”对比哈希和解法和双指针解法体会不同前置条件下策略如何切换。按这个顺序练完一遍你对找数题的体系认知会比零散刷题扎实得多。5. 找数题的“算法思想溢出”从排序到深度学习如果你觉得找数题的价值止步于刷题和面试那就太小看它了。它的思维模式实际上渗透在大量高级算法里从基础排序到现代人工智能到处都能看到找数题的影子。5.1 找数思维在排序算法里的身影很多排序算法内部其实都藏着找数的动作。快速排序的 partition 过程本质上是找一个“分割点”把比它小的放到左边比它大的放到右边这个分割点选得好不好直接影响排序效率。归并排序里合并两个有序数组时每一步也是在两个区间里“找出当前最小的元素”本质上就是一次二路找最小。堆排序里反复执行的堆调整每次都要在父节点和两个孩子之间找出最大值或最小值。可以这么说排序算法之所以需要比较和交换一部分原因就是它必须反复完成“在一组候选里找出应该放在当前位置的那个元素”这个任务而这正是找数思维的核心动作。从这个角度看找数题练的不是“会写二分”这一件事而是练“如何在候选集合里快速缩小范围并做出正确选择”的通用能力。这个能力在数据结构课程里贯穿始终在二叉搜索树里查找、在跳表里跳跃查找、在 B 树里按范围查找全部都是在用不同的结构加速同一个“找数”底层操作。5.2 在搜索算法、优化算法中的身影再往上层走找数思维遍布更广阔的算法场景。图论里的最短路算法每次从待处理集合中找出距离最小的节点相当于反复“找最小值”A* 搜索里每次从开放列表中找出 f 值最小的节点是一个带启发式信息的“找最优数”回溯算法里的剪枝本质上是做题前判断“这一侧不可能有答案”从而提前排除跟二分里“这一半不可能有 target”的判断思路同源。连深度学习里的优化过程也在做找数梯度下降每步朝着损失函数下降方向移动一点本质上是在高维空间里找损失最小的那个位置。各种改进算法比如带动量的优化器、自适应学习率的优化器都是在“找最小值”这个核心任务上做搜索策略的改良。理解了找数题里“搜索空间”和“缩小范围”这两个概念再看这些现代算法你会觉得它们的骨架并不神秘。所以我个人的体会是找数题对程序员的价值不在于背会那道题本身而在于它第一次帮你建立了“搜索空间”的直觉。要知道整个算法世界大到数据库索引小到一次循环里的 boolean 检查几乎都在做同样一件事从大量可能性中快速锁定答案。想明白这一点之后再遇到任何新算法我都习惯先用“它在搜索什么空间、用什么规则缩小空间”这两个问题去拆解往往很快就能抓住本质。这套思维就是找数题送给所有算法学习者的真正礼物。
