LeetCode 33. 搜刮旋转排序数组：二分查找的界限艺术

标题形貌

在旋转后的有序数组中搜刮目标值。假设数组原本按升序排列，但在某个未知下标处进行了旋转（例如 [0,1,2,4,5,6,7] 旋转后可能变为 [4,5,6,7,0,1,2]）。要求时间复杂度为 O(log n)。
示例：

1. 输入：nums = [4,5,6,7,0,1,2], target = 0  
2. 输出：4  
3. 解释：目标值 0 位于旋转后的右半部分。

复制代码

---

办理思路

旋转后的数组可视为两个有序子数组的组合。利用 二分查找 的关键在于判定哪一部分是有序的，并查抄目标值是否在该范围内。核心步骤如下：

• 判定有序区间：通过比力 nums[left] 和 nums[mid]，确定左半或右半是否有序。
  
• 缩小搜刮范围：根据目标值是否在有序区间内，调整左右指针。
  

---

代码实现

1. class Solution {
2.     public int search(int[] nums, int target) {
3.         int left = 0, right = nums.length - 1;
4.         while (left <= right) {
5.             int mid = left + (right - left) / 2;
6.             if (nums[mid] == target) return mid; // 直接命中
7.             
8.             // 判断左半部分是否有序
9.             if (nums[left] <= nums[mid]) {
10.                 // 目标值在左半有序区间内
11.                 if (target >= nums[left] && target < nums[mid]) {
12.                     right = mid - 1;
13.                 } else {
14.                     left = mid + 1;
15.                 }
16.             } else { // 右半部分有序
17.                 // 目标值在右半有序区间内
18.                 if (target > nums[mid] && target <= nums[right]) {
19.                     left = mid + 1;
20.                 } else {
21.                     right = mid - 1;
22.                 }
23.             }
24.         }
25.         return -1;
26.     }
27. }

复制代码

---

关键点剖析

1. 为什么用 nums[left] <= nums[mid]？

• 判定有序区间：
  若 nums[left] <= nums[mid]，说明左半部分 [left, mid] 是有序的（未包罗旋转点）。否则右半部分有序。
  
• 界限处理：
  当 left == mid 时（例如数组长度为 1），nums[left] == nums[mid]，等号确保这种环境被精确归类为“左半有序”。
  

2. 示例分析

案例 1：数组 [3, 1]，目标值 1

• left = 0, mid = 0，满意 nums[left] <= nums[mid]（3 ≤ 3）。
  
• 目标值不在左半部分（1 < 3 不成立），调整 left = mid + 1，终极找到目标值。
  

案例 2：数组 [5]，目标值 5

• 若去掉等号，条件 nums[left] < nums[mid] 不成立，程序误判右半有序。
  
• 查抄右半部分时，target > nums[mid] 不成立，错误调整 right = mid - 1，导致返回 -1。
  

---

界限条件处理

1. 单元素数组

当 nums.length == 1 时，left == mid == right，必须通过等号确保逻辑精确。
2. 完全有序数组

若数组未旋转（例如 [1,2,3,4,5]），逻辑仍能精确判定左半有序。
3. 严格递增与重复值

标题假设元素唯一，无需处理重复值。若存在重复值需调整条件（如 nums[left] < nums[mid]）。

---

常见疑问

Q：为什么不能利用 nums[left] < nums[mid]？

• 界限标题：当 left == mid 时，条件不成立，导致误判右半有序。
  
• 错误示例：
  数组 [5]，目标值 5。若用 <，程序错误调整 right = mid - 1，终极返回 -1。
  

---

总结

• 核心逻辑：通过 nums[left] <= nums[mid] 判定有序区间，结合目标值范围调整指针。
  
• 界限条件：等号处理 left == mid 的临界环境，确保单元素区间被精确辨认。
  
• 时间复杂度：O(log n)，每次循环将搜刮范围减半。
  

关键启示：二分查找的难点不仅在于算法框架，更在于对界限条件的精准处理。明白每一行代码背后的意图，才能避免“差之毫厘，谬以千里”。