022-搜索旋转排序数组 (Search in Rotated Sorted Array)

LeetCode 第22题 - 搜索旋转排序数组的详细题解，包含二分查找算法和JavaScript实现

题目描述

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 ≤ k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

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

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例

示例 1：

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2：

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

示例 3：

输入: nums = [1], target = 0
输出: -1

示例 4：

输入: nums = [1,3], target = 3
输出: 1

示例 5：

输入: nums = [3,1], target = 1
输出: 1

解题思路

二分查找法（推荐）

虽然数组被旋转了，但它仍然保持部分有序的特性。我们可以利用这个特性进行二分查找。

核心思想：

在旋转数组中，至少有一半是有序的
通过比较中间元素和边界元素，可以确定哪一半是有序的
如果目标值在有序的一半中，就在那一半中查找
如果目标值不在有序的一半中，就在另一半中查找

算法步骤：

使用二分查找，每次比较中间元素和边界元素
确定哪一半是有序的
判断目标值是否在有序的一半中
根据判断结果调整查找范围

JavaScript 解决方案

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        // 找到目标值
        if (nums[mid] === target) {
            return mid;
        }
        
        // 判断左半部分是否有序
        if (nums[left] <= nums[mid]) {
            // 左半部分有序
            if (nums[left] <= target && target < nums[mid]) {
                // 目标值在左半部分
                right = mid - 1;
            } else {
                // 目标值在右半部分
                left = mid + 1;
            }
        } else {
            // 右半部分有序
            if (nums[mid] < target && target <= nums[right]) {
                // 目标值在右半部分
                left = mid + 1;
            } else {
                // 目标值在左半部分
                right = mid - 1;
            }
        }
    }
    
    // 没有找到目标值
    return -1;
};

复杂度分析

时间复杂度：O(log n)

使用二分查找，每次将查找范围缩小一半
总共进行 O(log n) 次比较

空间复杂度：O(1)

只使用了常数额外空间

测试用例

// 测试函数
function testSearch() {
    const testCases = [
        { nums: [4,5,6,7,0,1,2], target: 0, expected: 4 },
        { nums: [4,5,6,7,0,1,2], target: 3, expected: -1 },
        { nums: [1], target: 0, expected: -1 },
        { nums: [1,3], target: 3, expected: 1 },
        { nums: [3,1], target: 1, expected: 1 },
        { nums: [5,1,3], target: 3, expected: 2 },
        { nums: [5,1,3], target: 5, expected: 0 },
        { nums: [5,1,3], target: 1, expected: 1 },
        { nums: [4,5,6,7,8,1,2,3], target: 8, expected: 4 },
        { nums: [4,5,6,7,8,1,2,3], target: 1, expected: 5 },
        { nums: [4,5,6,7,8,1,2,3], target: 3, expected: 7 },
        { nums: [4,5,6,7,8,1,2,3], target: 9, expected: -1 }
    ];
    
    testCases.forEach((testCase, index) => {
        const result = search(testCase.nums, testCase.target);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '✅' : '❌'}`);
        console.log(`输入: nums = [${testCase.nums}], target = ${testCase.target}`);
        console.log(`期望: ${testCase.expected}`);
        console.log(`实际: ${result}`);
        console.log('---');
    });
}

// 运行测试
testSearch();

关键点总结

有序性判断：通过比较中间元素和边界元素判断哪一半是有序的
目标值定位：根据有序性判断目标值在哪一半中
边界处理：注意等号的使用，确保不遗漏元素
旋转特性：利用旋转数组的部分有序特性
二分查找：在有序部分进行标准的二分查找

总结

这道题是二分查找的经典应用，考察了对旋转数组特性的理解和二分查找的灵活运用。

考察重点：

二分查找算法的应用
旋转数组的特性分析
有序性判断的逻辑
边界条件的处理
代码的简洁性和可读性

这道题是很多面试中的常见题目，掌握旋转数组的二分查找技巧对于解决类似问题很有帮助。在实际面试中，建议先分析旋转数组的特性，然后设计二分查找算法。

022-搜索旋转排序数组 (Search in Rotated Sorted Array)

On this page