二分查找的三重变奏：有序区间、旋转最小值与平方根——从“猜数字”到“向量检索”的思维演化

【学习记录】二分查找的三重变奏：有序区间、旋转最小值与平方根——从“猜数字”到“向量检索”的思维演化

如果你觉得二分查找只是一道“平平无奇的模板题”，那你可能还没有见过它的全貌。今天我们把三道经典的二分变体题放在一起：搜索旋转排序数组（LeetCode 33）、寻找旋转排序数组中的最小值（LeetCode 153）和x 的平方根（LeetCode 69）。它们分别代表了二分查找的三种高级应用场景：在无序中找有序区间、在旋转中找极值点、在连续空间中找整数边界。这三道题合在一起，几乎覆盖了二分查找的所有非标准形态。本文依然从比喻出发，逐层拆解，并连接到大模型时代的核心操作——向量检索中的有序性假设与近似搜索。

📌 目录

1. 题目一：搜索旋转排序数组（LeetCode 33）
   • 从熟悉到陌生：魔方旋转的比喻
   • 核心概念解析（三层递进）
   • 代码实现
   • 图解
   • 关键洞察
2. 题目二：寻找旋转排序数组中的最小值（LeetCode 153）
   • 从熟悉到陌生：山谷寻底的比喻
   • 核心概念解析
   • 代码实现
   • 关键洞察
3. 题目三：x 的平方根（LeetCode 69）
   • 从熟悉到陌生：数轴测量的比喻
   • 核心概念解析
   • 代码实现
   • 关键洞察
4. 知识图谱扩展：二分查找与大模型向量检索
5. 三句话带走
6. 留给你的思考题

一、搜索旋转排序数组（LeetCode 33）

题目描述

整数数组nums按升序排列，数组中的值互不相同。在传递给函数之前，nums在某个未知的下标k（0 <= k < nums.length）上进行了旋转，使数组变为[nums[k], nums[k+1], ..., 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,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmid# 判断左半是否有序ifnums[left]<=nums[mid]:# 左半有序，判断 target 是否在左半ifnums[left]<=target<nums[mid]:right=mid-1else:left=mid+1else:# 右半有序，判断 target 是否在右半ifnums[mid]<target<=nums[right]:left=mid+1else:right=mid-1return-1

执行过程（以nums = [4,5,6,7,0,1,2],target = 0为例）：

left=0, right=6, mid=3, nums[mid]=7 nums[left]=4 <= 7 → 左半 [4,5,6,7] 有序 target=0 是否在 [4,7] 内？否 → left = mid+1 = 4 left=4, right=6, mid=5, nums[mid]=1 nums[left]=0 <= 1 → 左半 [0,1] 有序 target=0 是否在 [0,1] 内？是 → right = mid-1 = 4 left=4, right=4, mid=4, nums[mid]=0 → 找到！返回 4

本质层（What）：分段有序的二分搜索

这道题的本质是：在“两个有序段”拼接的数组中，如何通过二分定位 target。

关键判断是nums[left] <= nums[mid]：

• 如果为真，说明左半部分是完全有序的。
• 否则，右半部分一定是有序的。

这个判断利用了旋转数组的一个核心性质：被旋转后，从任意中间点切开，至少有一半是单调递增的。

代码实现（Python）

defsearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidifnums[left]<=nums[mid]:# 左半有序ifnums[left]<=target<nums[mid]:right=mid-1else:left=mid+1else:# 右半有序ifnums[mid]<target<=nums[right]:left=mid+1else:right=mid-1return-1

图解

nums = [4, 5, 6, 7, 0, 1, 2], target = 0 第一次二分： [4, 5, 6, 7] [0, 1, 2] ↑ mid=7 左半有序 (4,5,6,7)，target=0 不在其中 → 搜索右半 第二次二分： [0, 1] [2] ↑ mid=1 左半有序 (0,1)，target=0 在其中 → 搜索左半 第三次二分： [0] ↑ 找到！

关键洞察

1. “至少一半有序”是旋转数组的救命稻草：标准二分依赖“全局有序”，而旋转数组提供了“至少一半有序”的弱条件，足以让 O(log n) 的搜索成为可能。

2. 判断有序的关键是nums[left] <= nums[mid]：在数组互不相同的情况下，这个条件足以判断左半是否有序。如果左半无序，右半必然有序。

3. 与暴力法的对比：暴力法 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,right=0,len(nums)-1whileleft<right:mid=(left+right)//2ifnums[mid]>nums[right]:left=mid+1else:right=midreturnnums[left]

执行过程（以nums = [3,4,5,1,2]为例）：

left=0, right=4, mid=2, nums[mid]=5 nums[mid] > nums[right]? 5 > 2 → 是 → left = mid+1 = 3 left=3, right=4, mid=3, nums[mid]=1 nums[mid] > nums[right]? 1 > 2 → 否 → right = mid = 3 left=3, right=3 → 退出循环，返回 nums[3]=1

本质层（What）：找“下降沿”的位置

这道题的本质是：在一个两段上升的数组中，找到唯一一处“上升趋势被打破”的位置。这个位置就是最小值。

这个“与右端点比较”的策略，比“与左端点比较”更加稳健，因为它利用了数组整体的单调性趋势。

代码实现（Python）

deffindMin(nums):left,right=0,len(nums)-1whileleft<right:mid=(left+right)//2ifnums[mid]>nums[right]:left=mid+1else:right=midreturnnums[left]

关键洞察

1. nums[mid] > nums[right]是本题的“灵魂条件”：它直接告诉我们最小值在左半还是右半。

2. 与 LeetCode 33 的对比：

   • 33 题：要找到target，需要判断哪一半有序，再判断target是否在有序半区。
   • 153 题：要找最小值，只需比较nums[mid]和nums[right]，无需关心target。

3. 终止条件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，但(mid+1)²超过x。

这本质上是一个“边界搜索”问题：在有序的整数区间[0, x]中，找满足mid² <= x的最大mid。

这就是二分查找最经典的应用之一——在有序空间中寻找满足条件的边界。

核心概念解析（三层递进）

直觉层（Why）：为什么用二分做平方根？

暴力法是从0开始逐个尝试（O(√x)），而二分法在[0, x]区间上不断逼近答案，时间复杂度 O(log x)，速度呈指数级优势。

机制层（How）：代码执行时的“时间切片”

defmySqrt(x):ifx<2:returnx left,right=2,x//2whileleft<=right:mid=(left+right)//2square=mid*midifsquare==x:returnmidelifsquare<x:left=mid+1else:right=mid-1returnright

执行过程（以x = 8为例）：

x=8, left=0, right=8, mid=4, square=16 > 8 → right=3 left=0, right=3, mid=1, square=1 < 8 → left=2 left=2, right=3, mid=2, square=4 < 8 → left=3 left=3, right=3, mid=3, square=9 > 8 → right=2 退出循环，返回 right=2

本质层（What）：在有序区间中寻找边界

这道题的本质是：在一个单调递增的序列[0, 1, 2, ..., x]中，找到最后一个满足mid² <= x的元素。

这就是二分查找中“找右边界”的经典模板：

1. 如果mid² == x，直接返回。
2. 如果mid² < x，继续向右搜索（left = mid + 1）。
3. 如果mid² > x，继续向左搜索（right = mid - 1）。

代码实现（Python）

解法一：标准二分（推荐）

defmySqrt(x):ifx<2:returnx left,right=2,x//2whileleft<=right:mid=(left+right)//2square=mid*midifsquare==x:returnmidelifsquare<x:left=mid+1else:right=mid-1returnright

解法二：牛顿迭代法（数学优化）

defmySqrt(x):ifx<2:returnx r=xwhiler>x//r:r=(r+x//r)//2returnr

牛顿迭代法的速度更快，但需要理解数学原理。面试中给出二分法已经足够，如果能主动提出“还有牛顿迭代法”，会是加分项。

关键洞察

1. 注意整数溢出：在 C++/Java 中，mid * mid可能溢出（当x接近 2³¹-1 时）。Python 的int无限大，没有这个问题，但在其他语言中需要写成mid > x // mid以避免溢出。

2. 边界条件x < 2：当x为 0 或 1 时，平方根就是它本身，直接返回，避免后续复杂逻辑。

3. 与“寻找旋转排序数组最小值”的对比：

   • 153 题：在无序数组中找极值点。
   • 69 题：在有序区间中找边界。
   • 两者的共同点：都在单调性（或分段单调）的基础上，用二分缩小搜索范围。

四、知识图谱扩展：二分查找与大模型向量检索

在 AI 领域，尤其是向量检索（Vector Search）中，二分查找的思想无处不在。

4.1 有序性假设是二分的基础

二分查找的核心前提是数据有序。在向量检索中，虽然高维向量没有“全局有序”的概念，但我们通过量化（Quantization）和聚类（Clustering）等技术，将向量空间划分成有序的桶（bucket），然后在桶内进行近似搜索。

4.2 “与右端点比较”的跨领域映射

在 LeetCode 153 中，我们通过nums[mid] > nums[right]来判断最小值在左半还是右半。这个“边界比较”的思想在向量检索中也有对应：

• HNSW（层级可导航小世界图）构建了多层图结构，在每一层中，搜索路径的选择基于当前节点与目标节点的距离比较，类似于“向更近的方向移动”。
• 量化感知的索引结构（如 PQ）在粗量化阶段，通过比较查询向量与聚类中心的距离，来决定搜索哪些桶。

4.3 平方根的“边界搜索”与模型量化

mySqrt实际上是在一个单调区间中找“满足条件的最大整数”。这在模型量化（Quantization）中也有类似应用：将浮点数映射到低精度的整数时，我们需要找到一个“阈值边界”——这正是二分查找的用武之地。

五、三句话带走

搜索旋转排序数组（33）

1. 直觉：旋转数组像被打乱的魔方，但切开后总有一半是有序的。
2. 机制：每次二分判断左半是否有序，再判断 target 是否在有序半区。
3. 本质：在“分段有序”的数组中，利用“至少一半有序”的性质进行二分。

寻找旋转排序数组中的最小值（153）

1. 直觉：在 V 形山谷中找谷底，通过比较当前点和右端点来判断方向。
2. 机制：nums[mid] > nums[right]则最小值在右半，否则在左半（含 mid）。
3. 本质：找“唯一一处上升趋势被打破的位置”，即最小值。

x 的平方根（69）

1. 直觉：在数轴上找一个数，使得它的平方刚好不超过目标值。
2. 机制：二分查找[0, x]区间，找满足mid² <= x的最大整数。
3. 本质：在有序区间中寻找边界，是“查找右边界”的经典模板。

六、留给你的思考题

问题 1（拓展）：在 LeetCode 33 中，如果数组元素可以重复（LeetCode 81），二分查找还能正常工作吗？如果不能，你会如何处理？

提示：当nums[left] == nums[mid] == nums[right]时，我们无法判断哪一半有序，只能将边界收缩一步（left++和right--）。最坏情况下复杂度退化为 O(n)。

问题 2（跨领域）：在向量检索中，如果查询向量落在“聚类边界”上，如何保证不会遗漏最近邻？

提示：这就是为什么 IVF（倒排索引）中需要设置nprobe参数（搜索的聚类数量），以覆盖可能遗漏的边界区域。nprobe 越大，召回率越高，但耗时也越长——这是“精度与效率的权衡”。

连接到大模型：在大模型的注意力机制中，top-k稀疏注意力也是在有限的计算资源下，通过选择最重要的 k 个 token 来近似全局注意力。这和向量检索中设置nprobe来平衡召回率和延迟，是不是有异曲同工之妙？🤔