27. Pivoted Search

Origin: Pivoted Search

Given a sorted array of unique integers that has been rotated at an unknown pivot, find the index of a target value or return -1 if not found.

本质是”旋转排序数组搜索”（LeetCode 33）。数组原本是严格递增的，在某个未知位置旋转了一下，比如 [1,2,3,4,5] 旋转后变成 [4,5,1,2,3]。

Example

Input: nums = [1609466400, 1609470000, 1609473600, 1609459200, 1609462800], target = 1609459200

Output: 3

Explanation: 在旋转数组上做二分查找。mid=2，左半 [0..2] 有序，target 不在左半范围里，搜右半。mid=3，nums[3]=target，返回 3。

Input Format

三行输入：

• 第一行：n（数组长度）
• 第二行：nums 数组元素
• 第三行：target

Constraints

• 0 <= nums.length <= 100000
• 0 <= nums[i] <= 10
• 所有元素唯一
• nums 是严格递增数组在未知位置旋转得到的
• 0 <= target <= 10

Output Format

返回 target 的 0-based 索引，不存在返回 -1。

Sample Input 0

0
5

Sample Output 0

-1

Sample Input 1

1
100
100

Sample Output 1

0

---

函数契约

// 输入：nums（旋转后的有序数组，元素唯一），target（目标值）
// 输出：target 的索引，不存在返回 -1
// 边界：空数组 → -1；单元素 → 匹配返回 0 否则 -1；未旋转（pivot=0）→ 普通二分

边界表

场景	返回什么
空数组	-1
单元素匹配	0
单元素不匹配	-1
target 不在数组中	-1
正常场景	target 的索引

Resolution

我的解法

function searchRotatedTimestamps(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) return mid;
        if (nums[mid] >= nums[left]) {
            // 左半有序
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;  // target 在左半范围内，搜左半
            } else {
                left = mid + 1;   // 不在，搜右半
            }
        } else {
            // 右半有序
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;   // target 在右半范围内，搜右半
            } else {
                right = mid - 1;  // 不在，搜左半
            }
        }
    }
    return -1;
}

解题思路

旋转数组的关键性质：虽然整体无序，但一半一定有序。

每次取 mid：

1. nums[left] <= nums[mid] → 左半有序，判断 target 在不在左半范围 nums[left] <= target < nums[mid]
2. nums[mid] < nums[right] → 右半有序，判断 target 在不在右半范围 nums[mid] < target <= nums[right]
3. 在有序范围内就搜那半，不在就搜另一半

为什么必须判断范围？ 只比较 target 和 nums[mid] 的大小不够。比如 [4,5,1,2,3] target=4，mid=2，nums[mid]=1，target > nums[mid] 就去搜右半——但 4 在左半。必须用有序那半的范围来缩小搜索区间。

踩坑经历

第一版只比较 target 和 nums[mid] 的大小，没有利用有序那半的范围，导致 3 个测试失败。修复方法：判断 target 是否落在有序那半的范围里（含边界）。

复杂度

• 时间：O(log n)，每次砍掉一半
• 空间：O(1)，只用几个变量

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题目：5. Target Index Search — 普通二分查找，第 27 题是旋转数组的二分查找