这是一个经典的二分查找算法题目。由于数组被旋转过，但它仍然具有一定的有序性（至少有一半是有序的），我们可以利用这个特性来实现 $O(\log n)$ 的查找。

解题思路

1. 二分查找：定义两个指针 left 和 right，分别指向数组的开头和结尾。
2. 判断有序区间：每次取中间位置 mid。
   • 因为数组经过旋转，[left, mid] 和 [mid, right] 中必然有一部分是有序的。
   • 如果 nums[left] <= nums[mid]，说明左半部分 [left, mid] 是有序的。
   • 否则，说明右半部分 [mid, right] 是有序的。
3. 判断 target 所在位置：
   • 如果左半部分有序：
     • 判断 target 是否在左半部分的范围内（nums[left] <= target < nums[mid]）。
     • 如果在，则将搜索范围缩小到左半部分 (right = mid - 1)。
     • 如果不在，则搜索右半部分 (left = mid + 1)。
   • 如果右半部分有序：
     • 判断 target 是否在右半部分的范围内（nums[mid] < target <= nums[right]）。
     • 如果在，则将搜索范围缩小到右半部分 (left = mid + 1)。
     • 如果不在，则搜索左半部分 (right = mid - 1)。
4. 循环终止：当 left > right 时，说明没找到，返回 -1。如果中间找到，直接返回下标。

JavaScript 代码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        // 如果中间值就是目标值，直接返回索引
        if (nums[mid] === target) {
            return mid;
        }
        // 判断哪一部分是有序的
        // 注意：由于元素互不相同，这里用 <= 还是 < 都可以，
        // 但通常为了逻辑严谨（防止 left == mid 时判定错误），用 <= 确保左边被完全涵盖
        if (nums[left] <= nums[mid]) {
            // 左半部分 [left, mid] 是有序的
            
            // 判断 target 是否在左半部分的区间内
            if (nums[left] <= target && target < nums[mid]) {
                // target 在左侧
                right = mid - 1;
            } else {
                // target 在右侧
                left = mid + 1;
            }
        } else {
            // 右半部分 [mid, right] 是有序的
            
            // 判断 target 是否在右半部分的区间内
            if (nums[mid] < target && target <= nums[right]) {
                // target 在右侧
                left = mid + 1;
            } else {
                // target 在左侧
                right = mid - 1;
            }
        }
    }
    // 未找到目标值
    return -1;
};

复杂度分析

• 时间复杂度: $O(\log n)$。我们每次循环都将搜索范围缩小一半，这是标准的二分查找复杂度。
• 空间复杂度: $O(1)$。我们只使用了常数级别的额外变量（left, right, mid）。

示例演示 (nums = [4,5,6,7,0,1,2], target = 0)

1. 第一轮: left=0, right=6, mid=3 (值为7)。
   • nums[left]=4 <= nums[mid]=7，说明左边 [4,5,6,7] 有序。
   • target=0 不在 [4, 7) 之间。
   • 所以去右边找，left 变为 mid + 1 = 4。
2. 第二轮: left=4, right=6, mid=5 (值为1)。
   • nums[left]=0 <= nums[mid]=1，说明左边 [0, 1] 有序。
   • target=0 在 [0, 1) 之间。
   • 所以去左边找，right 变为 mid - 1 = 4。
3. 第三轮: left=4, right=4, mid=4 (值为0)。
   • nums[mid] === target，返回 4。