LeetCode 笔记：LC33 和二分查找的特殊模板

0724 LeetCode 笔记：LC33 和二分查找的特殊模板

本文由 AI 生成 ，存在修改。真实创作日期为 2025.07.24

目录

• 一、 问题：LeetCode 33 搜索旋转排序数组
• 二、 二分查找两大模板对比
• 三、 例题：不同题目如何选择不同模板？

一、 问题：LeetCode 33 搜索旋转排序数组

此题的难点在于，数组经过旋转后，整体不再单调，常规二分查找失效。例如 [4,5,6,7,0,1,2]。

记忆关键词：

1. 锚点 (Anchor): 选取数组最后一个元素 nums[n-1] 作为基准。
2. 逻辑分区 (Logical Partitioning): 根据与“锚点”的比较，将数组和 target 划分为两个逻辑区域：大数区 (> 锚点) 和 小数区 (<= 锚点)。
3. 性质构造 (Property Construction): check 函数的作用就是构造一个虚拟的布尔数组，形式必为 [false, false, ..., true, true]。二分查找的目标就是找到第一个 true 的位置。
4. 边界查找 (Boundary Search): 使用 left+1<right 的二分模板，其设计目的就是精确查找这种性质的边界。

check 函数本质：判断 nums[mid] 是否在 target 的“逻辑右侧”。如果 nums[mid] 和 target 在锚点的不同侧，或者在同一侧但 nums[mid] >= target，则 check 返回 true，意味着答案可能在左半区，于是收缩 right=mid。

二、 二分查找两大模板对比

特性	模板一：通用边界查找 (right = n)	模板二：封装安全查找 (right = n-1)
right 初始值	nums.length (逻辑上的越界值)	nums.length - 1 (最后一个有效索引)
** 返回值范围**	逻辑区间 [0, n]，允许返回 n	物理区间 [0, n-1]，结果必在索引内
返回值含义	边界/插入点，可能返回 n（含义是 target 的插入位置）	在模板一返回 n 的情况下返回 n - 1 （这个数没有任何含义），可以在函数内部判断后返回 -1
边界检查责任	调用者 (必须检查返回的 right 是否越界)	只需要检查 nums[right] 是否等于 target，无需检查越界
设计哲学	抽象与复用：作为通用工具，返回丰富信息	封装与安全：作为自包含方案，返回最终答案（内部判断是否等于的情况下）
适用场景	实现 lower_bound, upper_bound 等通用函数	“找到返回索引，找不到返回-1” 的具体问题
对空数组处理	天然安全 (返回 0)	必须显式处理，否则 n-1 会出错

可以理解为，模板二是模板一的特殊情况，在不需要运用到 lowerBound 通用性质的情况下，这么做可以简化边界检查。

三、 例题：不同题目如何选择不同模板？

• searchRange (在排序数组中查找元素的第一个和最后一个位置)（LeetCode 34）

  • 选用模板一，因为它将问题抽象为两次调用通用的 lowerBound 函数。用到了 lowerBound 的关键性质——返回插入点。
  • lowerBound 被设计成一个可复用的工具，必须能处理所有情况（包括返回 nums.length），因此采用模板一最合适。

• search (搜索旋转排序数组)（LeetCode 33、153 等等）

  • 选用模板二，因为它是一个封装好的、自包含的解决方案。
  • 所有逻辑（包括复杂的 check 函数）都在方法内部，目标明确，无需返回“插入点”这类额外信息。
  • 模板二能保证内部索引访问的绝对安全，并直接返回最终结果 -1 或目标索引，代码更简洁。

总结：当需要构建一个可复用的通用工具时，选择模板一；当要解决一个特定的、自包含的问题时，选择模板二更安全、更直接。