题目描述

题目链接：33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

例子

例子 1

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

例子 2

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

例子 3

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

Constraints

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is guaranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

解题思路

题目提示可以在 O(log n) 下完成，所以显然需要使用二分查找，二分查找的过程很简单：固定左右边界，用中间值与目标值判断大小，根据情况收缩左边界或者右边界即可。在整个数组单调的情况下比较清晰，但现在数组分成了两部分各自单调，所以需要具体讨论不同情况：

这里以当中间值 Mid > Target 为例，有以下情况：

图中两部分数组用颜色区分出来，Target 可能的位置用箭头标识出来，可以发现 Target 出现在 Mid 右侧的情况只有一种可能：Left 到 Mid 为单调递增（排除中间情况），并且 Left 也比 Target 大（排除另外两种情况），此时收缩左边界，其余情况通通收缩右边界即可。对于 Mid < Target 也可以通过画图进行同样的分析，这里不赘述。

代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                if (nums[right] < target && nums[mid] <= nums[right]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[left] > target && nums[mid] >= nums[left]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
};

• 时间复杂度: O(log n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 33.SearchInRotatedSortedArray.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions