【学习记录】二分查找的三重变奏有序区间、旋转最小值与平方根——从“猜数字”到“向量检索”的思维演化如果你觉得二分查找只是一道“平平无奇的模板题”那你可能还没有见过它的全貌。今天我们把三道经典的二分变体题放在一起搜索旋转排序数组LeetCode 33、寻找旋转排序数组中的最小值LeetCode 153和x 的平方根LeetCode 69。它们分别代表了二分查找的三种高级应用场景在无序中找有序区间、在旋转中找极值点、在连续空间中找整数边界。这三道题合在一起几乎覆盖了二分查找的所有非标准形态。本文依然从比喻出发逐层拆解并连接到大模型时代的核心操作——向量检索中的有序性假设与近似搜索。 目录题目一搜索旋转排序数组LeetCode 33从熟悉到陌生魔方旋转的比喻核心概念解析三层递进代码实现图解关键洞察题目二寻找旋转排序数组中的最小值LeetCode 153从熟悉到陌生山谷寻底的比喻核心概念解析代码实现关键洞察题目三x 的平方根LeetCode 69从熟悉到陌生数轴测量的比喻核心概念解析代码实现关键洞察知识图谱扩展二分查找与大模型向量检索三句话带走留给你的思考题一、搜索旋转排序数组LeetCode 33题目描述整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在某个未知的下标k0 k nums.length上进行了旋转使数组变为[nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。给你旋转后的数组nums和一个整数target如果target在数组中存在返回它的下标否则返回-1。示例输入nums [4,5,6,7,0,1,2], target 0 输出4 输入nums [4,5,6,7,0,1,2], target 3 输出-1从熟悉到陌生魔方旋转的比喻想象你有一排按顺序摆放的书[0,1,2,3,4,5,6,7]。你从中间某个位置把书分成两堆然后把右边那堆搬到左边来旋转变成了[4,5,6,7,0,1,2]。现在你要找一本书target。书虽然整体被打乱了但有一个关键性质被旋转后的数组从中间切开总有一半是“正常有序”的。如果target落在有序的那一半你就在那一半里继续二分。如果不在就转向另一半虽然它也是旋转的但你可以递归地应用同样的逻辑。这就是“搜索旋转排序数组”的核心策略每次二分都先判断哪一半是有序的然后决定 target 在哪一半。核心概念解析三层递进直觉层Why为什么旋转数组还能用二分标准二分要求数组全局有序。旋转数组虽然全局无序但具有分段有序的特性——从任意中间位置切开至少有一半是完全有序的。我们可以利用这个性质每次都将搜索范围缩小到有序的那一半或另一半从而保持 O(log n) 的时间复杂度。机制层How代码执行时的“时间切片”defsearch(nums,target):left,right0,len(nums)-1whileleftright:mid(leftright)//2ifnums[mid]target:returnmid# 判断左半是否有序ifnums[left]nums[mid]:# 左半有序判断 target 是否在左半ifnums[left]targetnums[mid]:rightmid-1else:leftmid1else:# 右半有序判断 target 是否在右半ifnums[mid]targetnums[right]:leftmid1else:rightmid-1return-1执行过程以nums [4,5,6,7,0,1,2],target 0为例left0, right6, mid3, nums[mid]7 nums[left]4 7 → 左半 [4,5,6,7] 有序 target0 是否在 [4,7] 内否 → left mid1 4 left4, right6, mid5, nums[mid]1 nums[left]0 1 → 左半 [0,1] 有序 target0 是否在 [0,1] 内是 → right mid-1 4 left4, right4, mid4, nums[mid]0 → 找到返回 4本质层What分段有序的二分搜索这道题的本质是在“两个有序段”拼接的数组中如何通过二分定位 target。关键判断是nums[left] nums[mid]如果为真说明左半部分是完全有序的。否则右半部分一定是有序的。这个判断利用了旋转数组的一个核心性质被旋转后从任意中间点切开至少有一半是单调递增的。代码实现Pythondefsearch(nums,target):left,right0,len(nums)-1whileleftright:mid(leftright)//2ifnums[mid]target:returnmidifnums[left]nums[mid]:# 左半有序ifnums[left]targetnums[mid]:rightmid-1else:leftmid1else:# 右半有序ifnums[mid]targetnums[right]:leftmid1else:rightmid-1return-1图解nums [4, 5, 6, 7, 0, 1, 2], target 0 第一次二分 [4, 5, 6, 7] [0, 1, 2] ↑ mid7 左半有序 (4,5,6,7)target0 不在其中 → 搜索右半 第二次二分 [0, 1] [2] ↑ mid1 左半有序 (0,1)target0 在其中 → 搜索左半 第三次二分 [0] ↑ 找到关键洞察“至少一半有序”是旋转数组的救命稻草标准二分依赖“全局有序”而旋转数组提供了“至少一半有序”的弱条件足以让 O(log n) 的搜索成为可能。判断有序的关键是nums[left] nums[mid]在数组互不相同的情况下这个条件足以判断左半是否有序。如果左半无序右半必然有序。与暴力法的对比暴力法 O(n)二分法 O(log n)。如果面试中你只写出了暴力法说明你没有抓住“有序”这个隐藏条件。二、寻找旋转排序数组中的最小值LeetCode 153题目描述已知一个长度为n的数组预先按升序排列经由1到n次旋转后得到输入数组。例如原数组[0,1,2,4,5,6,7]在旋转4次后可能变为[4,5,6,7,0,1,2]。请找出并返回数组中的最小元素。数组中的元素互不相同。示例输入nums [3,4,5,1,2] 输出1 输入nums [4,5,6,7,0,1,2] 输出0从熟悉到陌生山谷寻底的比喻想象你在一个山谷中从山顶往下走经过谷底再爬上另一座山。整个路径是V 形的——先下降后上升。你被蒙上眼睛但可以随时感知脚下的坡度。你的任务是找到谷底的位置最小值。你的策略如果你站在一个点发现它比右边的点高说明你还在下降阶段谷底在右边你就往右走。如果你发现它比右边的点低说明你已经过了谷底正在上升阶段你就往左走。这就是“寻找旋转数组最小值”的核心思路用二分查找不断缩小“谷底”可能出现的范围。核心概念解析三层递进直觉层Why为什么用nums[mid] nums[right]判断在旋转数组中最小值就是唯一一个“打破升序”的点。如果我们看数组的最后一位nums[right]如果nums[mid] nums[right]说明mid在左半较大的部分最小值在右半 →left mid 1。如果nums[mid] nums[right]说明mid在右半较小的部分最小值在左半包括mid→right mid。这个判断利用了旋转数组的“两段上升、中间断裂”的性质。机制层How代码执行时的“时间切片”deffindMin(nums):left,right0,len(nums)-1whileleftright:mid(leftright)//2ifnums[mid]nums[right]:leftmid1else:rightmidreturnnums[left]执行过程以nums [3,4,5,1,2]为例left0, right4, mid2, nums[mid]5 nums[mid] nums[right]? 5 2 → 是 → left mid1 3 left3, right4, mid3, nums[mid]1 nums[mid] nums[right]? 1 2 → 否 → right mid 3 left3, right3 → 退出循环返回 nums[3]1本质层What找“下降沿”的位置这道题的本质是在一个两段上升的数组中找到唯一一处“上升趋势被打破”的位置。这个位置就是最小值。判断条件结论nums[mid] nums[right]mid在左半大的部分最小值在右边nums[mid] nums[right]mid在右半小的部分最小值在左边含mid这个“与右端点比较”的策略比“与左端点比较”更加稳健因为它利用了数组整体的单调性趋势。代码实现PythondeffindMin(nums):left,right0,len(nums)-1whileleftright:mid(leftright)//2ifnums[mid]nums[right]:leftmid1else:rightmidreturnnums[left]关键洞察nums[mid] nums[right]是本题的“灵魂条件”它直接告诉我们最小值在左半还是右半。与 LeetCode 33 的对比33 题要找到target需要判断哪一半有序再判断target是否在有序半区。153 题要找最小值只需比较nums[mid]和nums[right]无需关心target。终止条件left right而非left right因为我们最终要找的是最小值的位置当left right时那个位置就是最小值。不需要额外检查中间值。三、x 的平方根LeetCode 69题目描述给你一个非负整数x计算并返回x的算术平方根。由于返回类型是整数结果只保留整数部分小数部分将被舍去。示例输入x 4 输出2 输入x 8 输出2 解释8 的平方根是 2.82842...由于返回类型是整数小数部分将被舍去。从熟悉到陌生数轴测量的比喻想象你在一个数轴上从0到x之间放了一把尺子。你要找一个数mid使得mid²刚好不超过x但(mid1)²超过x。这本质上是一个“边界搜索”问题在有序的整数区间[0, x]中找满足mid² x的最大mid。这就是二分查找最经典的应用之一——在有序空间中寻找满足条件的边界。核心概念解析三层递进直觉层Why为什么用二分做平方根暴力法是从0开始逐个尝试O(√x)而二分法在[0, x]区间上不断逼近答案时间复杂度 O(log x)速度呈指数级优势。机制层How代码执行时的“时间切片”defmySqrt(x):ifx2:returnx left,right2,x//2whileleftright:mid(leftright)//2squaremid*midifsquarex:returnmidelifsquarex:leftmid1else:rightmid-1returnright执行过程以x 8为例x8, left0, right8, mid4, square16 8 → right3 left0, right3, mid1, square1 8 → left2 left2, right3, mid2, square4 8 → left3 left3, right3, mid3, square9 8 → right2 退出循环返回 right2本质层What在有序区间中寻找边界这道题的本质是在一个单调递增的序列[0, 1, 2, ..., x]中找到最后一个满足mid² x的元素。这就是二分查找中“找右边界”的经典模板如果mid² x直接返回。如果mid² x继续向右搜索left mid 1。如果mid² x继续向左搜索right mid - 1。代码实现Python解法一标准二分推荐defmySqrt(x):ifx2:returnx left,right2,x//2whileleftright:mid(leftright)//2squaremid*midifsquarex:returnmidelifsquarex:leftmid1else:rightmid-1returnright解法二牛顿迭代法数学优化defmySqrt(x):ifx2:returnx rxwhilerx//r:r(rx//r)//2returnr牛顿迭代法的速度更快但需要理解数学原理。面试中给出二分法已经足够如果能主动提出“还有牛顿迭代法”会是加分项。关键洞察注意整数溢出在 C/Java 中mid * mid可能溢出当x接近 2³¹-1 时。Python 的int无限大没有这个问题但在其他语言中需要写成mid x // mid以避免溢出。边界条件x 2当x为 0 或 1 时平方根就是它本身直接返回避免后续复杂逻辑。与“寻找旋转排序数组最小值”的对比153 题在无序数组中找极值点。69 题在有序区间中找边界。两者的共同点都在单调性或分段单调的基础上用二分缩小搜索范围。四、知识图谱扩展二分查找与大模型向量检索在 AI 领域尤其是向量检索Vector Search中二分查找的思想无处不在。4.1 有序性假设是二分的基础二分查找的核心前提是数据有序。在向量检索中虽然高维向量没有“全局有序”的概念但我们通过量化Quantization和聚类Clustering等技术将向量空间划分成有序的桶bucket然后在桶内进行近似搜索。二分查找算法题向量检索RAG 系统在一维有序数组中查找 target在高维向量空间中查找最近邻数据必须有序通过 IVF倒排索引将向量聚类在每个聚类内搜索每次比较排除一半通过nprobe参数控制搜索的聚类数量时间复杂度 O(log n)时间复杂度 O(nprobe × log n_per_cluster)4.2 “与右端点比较”的跨领域映射在 LeetCode 153 中我们通过nums[mid] nums[right]来判断最小值在左半还是右半。这个“边界比较”的思想在向量检索中也有对应HNSW层级可导航小世界图构建了多层图结构在每一层中搜索路径的选择基于当前节点与目标节点的距离比较类似于“向更近的方向移动”。量化感知的索引结构如 PQ在粗量化阶段通过比较查询向量与聚类中心的距离来决定搜索哪些桶。4.3 平方根的“边界搜索”与模型量化mySqrt实际上是在一个单调区间中找“满足条件的最大整数”。这在模型量化Quantization中也有类似应用将浮点数映射到低精度的整数时我们需要找到一个“阈值边界”——这正是二分查找的用武之地。五、三句话带走搜索旋转排序数组33直觉旋转数组像被打乱的魔方但切开后总有一半是有序的。机制每次二分判断左半是否有序再判断 target 是否在有序半区。本质在“分段有序”的数组中利用“至少一半有序”的性质进行二分。寻找旋转排序数组中的最小值153直觉在 V 形山谷中找谷底通过比较当前点和右端点来判断方向。机制nums[mid] nums[right]则最小值在右半否则在左半含 mid。本质找“唯一一处上升趋势被打破的位置”即最小值。x 的平方根69直觉在数轴上找一个数使得它的平方刚好不超过目标值。机制二分查找[0, x]区间找满足mid² x的最大整数。本质在有序区间中寻找边界是“查找右边界”的经典模板。六、留给你的思考题问题 1拓展在 LeetCode 33 中如果数组元素可以重复LeetCode 81二分查找还能正常工作吗如果不能你会如何处理提示当nums[left] nums[mid] nums[right]时我们无法判断哪一半有序只能将边界收缩一步left和right--。最坏情况下复杂度退化为 O(n)。问题 2跨领域在向量检索中如果查询向量落在“聚类边界”上如何保证不会遗漏最近邻提示这就是为什么 IVF倒排索引中需要设置nprobe参数搜索的聚类数量以覆盖可能遗漏的边界区域。nprobe 越大召回率越高但耗时也越长——这是“精度与效率的权衡”。连接到大模型在大模型的注意力机制中top-k稀疏注意力也是在有限的计算资源下通过选择最重要的 k 个 token 来近似全局注意力。这和向量检索中设置nprobe来平衡召回率和延迟是不是有异曲同工之妙