题目地址

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

题目描述

给你一个升序排列的整数数组 nums ，和一个整数 target 。

假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。


示例 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


提示：

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4

题解

不按套路出牌

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; ++ i) {
            if (target == nums[i]) {
                return i;
            }
        }
        return -1;
    }
}

时间复杂度：O(n)，n 为数组 nums 的长度。

过了，再次证明了 leetcode 的执行用例不够完善。

二分搜索

看到关键词：数组，O(log n) 就应该想到二分搜索。

二分搜索的前提是数组有序，旋转后的排序数组可能看成两个有序的数组：

• (1) [nums[k], nums[k+1], ..., nums[n-1]
• (2) nums[0], nums[1], ..., nums[k-1]]

原数组按升序排列，nums[0] 是其最小值，所以我们第一步应该找到 nums[0]，也就是最小值所在的位置。
这样就可以把旋转后的数组分成两个有序的数组。

    public int getMinValueIndex(int[] nums) {
        int left = 1;
        int right = nums.length - 1;
        while (left < right) {
            // 因为 nums.length <= 50000，所以 (left + right) 不会溢出
            // 担心溢出可以通过以下方式计算 middle 索引
            // left + (right - left) / 2
            int middle = (left  + right) / 2;

            
            if (nums[middle] > nums[0]) {
                // 大于第一个数，说明处于第一个有序数组的范围，要向右移动 left
                left = middle + 1;
            } else if (nums[middle] < nums[0]){
                // 小于第一个数，说明处于第二个有序数组的范围，要向左移动 right
                right = middle;
            }
        }

        // left == right
        return nums[0] < nums[right] ? 0 : right;
    }

注意：搜索的范围是 [1, length - 1]，没有搜索位置 0。

完整代码如下所示：

class Solution {
    public int search(int[] nums, int target) {
        int minValueIndex = getMinValueIndex(nums);
        
        // case 1
        // 没有旋转为两个有序数组，还是一个有序数组
        if (minValueIndex == 0) {
            return binarySearch(nums, 0, nums.length - 1, target);
        }

        // case 2
        // target 处于第一个有序数组的范围
        if (target >= nums[0]) {
            return binarySearch(nums, 0, minValueIndex - 1, target);
        }

        // case 3
        // target 处于第二个有序数组的范围
        return binarySearch(nums, minValueIndex, nums.length - 1, target);
    }

    public int binarySearch(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }

        return -1;
    }

    public int getMinValueIndex(int[] nums) {
        int left = 1;
        int right = nums.length - 1;
        while (left < right) {
            // 因为 nums.length <= 50000，所以 (left + right) 不会溢出
            // 担心溢出可以通过以下方式计算 middle 索引
            // left + (right - left) / 2
            int middle = (left  + right) / 2;

            
            if (nums[middle] > nums[0]) {
                // 大于第一个数，说明处于第一个有序数组的范围，要向右移动 left
                left = middle + 1;
            } else if (nums[middle] < nums[0]){
                // 小于第一个数，说明处于第二个有序数组的范围，要向左移动 right
                right = middle;
            }
        }

        // left == right
        return nums[0] < nums[right] ? 0 : right;
    }
}

时间复杂度：O(log n)，n 为数组 nums 的长度。