搜索旋转排序数组

33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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

由于题目要求时间复杂度为O(log n)，这提示我们使用二分查找。

数组本身不是有序的，进行旋转后只是局部有序的，还能二分查找吗？

可以发现，我们将数组从中间分成左右两部分后，左右部分中一定有一个部分是有序的。例如示例中我们从 6 这个位置分开为[4,5,6] 和 [7,0,1,2] ，其中左边 [4,5,6] 这个部分的数组是有序的。

这启示我们可以在常规二分查找上改动，每次判断分割出来的两个部分，哪个是有序的，根据有序的部分改变二分搜索的上下界。

• 如果 [1, mid-1] 是有序数组，且 target 的大小满足 [nums[l], nums[mid]) ，则我们将搜索范围缩小到 [1, mid-1] ，否则在[mid+1, r] 中寻找。
• 如果 [mid, r] 是有序数组，且 target 的大小满足 [nums[mid+1], nums[r]) ，则我们将搜索范围缩小到 [mid+1, r] ，否则在[1, mid-1] 中寻找。

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(n == 0)return -1;
        int l = 0, r = n - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] == target)return mid;
            //左边部分有序
            if(nums[0] <= nums[mid]){
                //target 在有序部分
                if(nums[0] <= target && target <= nums[mid]){
                    r = mid - 1;
                }else{//target 不在有序部分
                    l = mid + 1;
                }
            }else{//右边部分有序
                 //target 在有序部分
                if(nums[mid] <= target && target <= nums[n-1]){
                    l = mid + 1;
                }else{//target 不在有序部分
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

时间复杂度 O(logN)，空间复杂度 O(1)。