Search in Rotated Sorted Array（搜索旋转排序数组）

题目 / Problem

中文： 给定一个元素互不相同、原本按升序排列的整数数组 nums。

在传入函数之前，数组可能在未知下标 k 处进行左旋转：
Before being passed to the function, the array may be left-rotated at an unknown index k:

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

例如：
For example:

原数组 / Original: [0,1,2,4,5,6,7]
左旋 3 位 / Rotate left by 3: [4,5,6,7,0,1,2]

给定旋转后的数组 nums 和整数 target，如果目标值存在，返回它的下标；否则返回 -1。

算法的时间复杂度必须为 O(log n)。

English: There is an integer array nums sorted in ascending order with distinct values. Before being passed to the function, it may be left-rotated at an unknown index.

Given the possibly rotated array and an integer target, return the index of target if it exists, or -1 otherwise.

The algorithm must run in O(log n) time.

示例 / Examples

Example 1

Input:  nums = [4,5,6,7,0,1,2], target = 0
Output: 4

目标值 0 位于下标 4。
Target 0 is located at index 4.

Example 2

Input:  nums = [4,5,6,7,0,1,2], target = 3
Output: -1

数组中不存在目标值 3。
Target 3 does not exist in the array.

Example 3

Input:  nums = [1], target = 0
Output: -1

约束 / Constraints

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
nums 中所有值互不相同。
All values in nums are unique.
nums 是一个可能经过旋转的升序数组。
nums is an ascending array that may have been rotated.
-10⁴ <= target <= 10⁴

关键观察：至少一半有序 / Key Observation: At Least One Half Is Sorted

旋转后的数组整体不再有序，但对任意搜索区间 [left, right] 和中点 mid：
The rotated array is not globally sorted, but for any search interval [left, right] with midpoint mid:

[left, mid] 和 [mid, right] 中至少有一半保持升序。
At least one of [left, mid] and [mid, right] remains sorted.

例如：
For example:

[4,5,6,7,0,1,2]
 L     M     R

左半部分 [4,5,6,7] 有序
Left half [4,5,6,7] is sorted

利用有序的一半，可以判断 target 是否落在其数值范围内，并一次排除一半搜索区间。
The sorted half lets us determine whether target lies within its value range and eliminate half the search interval each time.

解题思路：改造二分查找 / Approach: Modified Binary Search

使用闭区间 [left, right]：
Use the closed interval [left, right]:

计算中点 mid。如果 nums[mid] === target，直接返回 mid。
Calculate mid. If nums[mid] === target, return mid.
判断哪一半有序。
Determine which half is sorted.
判断目标值是否位于有序半区的数值范围内。
Check whether the target lies within the sorted half's value range.
如果在，就保留该半区；否则搜索另一半。
If it does, keep that half; otherwise search the other half.

情况一：左半部分有序 / Case 1: Left Half Is Sorted

判断条件：
Condition:

nums[left] <= nums[mid]

如果：
If:

nums[left] <= target < nums[mid]

目标位于左半区，令 right = mid - 1；否则令 left = mid + 1。
The target lies in the left half, so set right = mid - 1; otherwise set left = mid + 1.

情况二：右半部分有序 / Case 2: Right Half Is Sorted

否则右半部分必然有序。如果：
Otherwise, the right half must be sorted. If:

nums[mid] < target <= nums[right]

目标位于右半区，令 left = mid + 1；否则令 right = mid - 1。
The target lies in the right half, so set left = mid + 1; otherwise set right = mid - 1.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (nums[left] <= nums[mid]) {
      // 左半部分有序 / Left half is sorted.
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // 右半部分有序 / Right half is sorted.
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

执行过程 / Walkthrough

Example 1：查找 `target = 0`

nums = [4,5,6,7,0,1,2]

步骤 / Step	`left`	`mid`	`right`	中点值 / `nums[mid]`	有序半区 / Sorted Half	操作 / Action
1	0	3	6	7	左 `[4,5,6,7]` / Left	`0` 不在 `[4,7)`，搜索右侧 / Search right
2	4	5	6	1	左 `[0,1]` / Left	`0` 在 `[0,1)`，搜索左侧 / Search left
3	4	4	4	0	—	找到，返回 `4` / Found; return `4`

Example 2：查找 `target = 3`

步骤 / Step	`left`	`mid`	`right`	中点值 / `nums[mid]`	操作 / Action
1	0	3	6	7	左侧有序，但 `3` 不在 `[4,7)`，搜索右侧 / Search right
2	4	5	6	1	左侧有序，但 `3` 不在 `[0,1)`，搜索右侧 / Search right
3	6	6	6	2	左侧有序，但 `3` 不在 `[2,2)`，令 `left = 7`

此时 left > right，搜索区间为空，返回 -1。
Now left > right, so the search interval is empty and the function returns -1.

为什么单元素区间也正确？ / Why Does a Single-Element Interval Work?

当 left === mid === right 时：
When left === mid === right:

如果该值等于目标，前面的相等判断直接返回。
If the value equals the target, the equality check returns immediately.
否则 nums[left] <= nums[mid] 成立，边界会移动并使区间变空。
Otherwise, nums[left] <= nums[mid] holds, and a boundary moves to empty the interval.

因此不需要单独处理长度为 1 的数组。
No special case is needed for an array of length 1.

为什么元素唯一很重要？ / Why Do Distinct Values Matter?

当元素互不相同时，可以通过 nums[left] <= nums[mid] 明确判断左半区有序；否则右半区有序。
With distinct values, nums[left] <= nums[mid] reliably identifies the sorted left half; otherwise, the right half is sorted.

如果允许大量重复值，例如：
If many duplicate values were allowed, such as:

[1,1,1,0,1]

当 nums[left] === nums[mid] === nums[right] 时，无法判断旋转点位于哪一侧，可能只能逐步缩小边界，最坏退化为 O(n)。本题保证元素唯一，因此不会出现这种歧义。
When nums[left] === nums[mid] === nums[right], the pivot side is ambiguous, potentially degrading the search to O(n). This problem guarantees distinct values, avoiding that issue.

复杂度 / Complexity

时间复杂度：O(log n)，每轮都排除约一半搜索区间。
Time: O(log n), because each iteration eliminates about half the search interval.
空间复杂度：O(1)，只使用常数个额外变量。
Space: O(1), because only a constant number of extra variables is used.

与普通二分查找的区别 / Difference from Ordinary Binary Search

普通二分查找可以直接通过 nums[mid] 与 target 的大小关系选择方向，因为整个数组有序。旋转数组只在局部有序，因此每轮需要先判断哪一半有序，再判断目标是否位于该半区。
Ordinary binary search selects a direction directly from the comparison between nums[mid] and target because the entire array is sorted. A rotated array is only locally sorted, so each iteration first identifies the sorted half and then checks whether the target belongs there.

易错点 / Common Pitfalls

每轮必须先检查 nums[mid] === target。
Check nums[mid] === target before choosing a half.
左半区有序的判断是 nums[left] <= nums[mid]，需要包含等号以处理单元素区间。
Use nums[left] <= nums[mid] to identify a sorted left half, including equality for single-element intervals.
左半区的目标范围是 nums[left] <= target && target < nums[mid]。
The target range for the left half is nums[left] <= target && target < nums[mid].
右半区的目标范围是 nums[mid] < target && target <= nums[right]。
The target range for the right half is nums[mid] < target && target <= nums[right].
更新边界时要排除已经比较过的 mid，使用 mid + 1 或 mid - 1。
Exclude the already checked mid when updating boundaries by using mid + 1 or mid - 1.
数组可能完全没有旋转，算法仍应正常工作。
The array may not be rotated at all; the algorithm must still work.

Search in Rotated Sorted Array