33. 搜索旋转排序数组

1.题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:

示例 2:

2.思路

1.如果数组为空，返回-1，如果数组只有一个元素，则判断这个元素是否为target，是则返回0，否则返回-1。
2.先寻找数组旋转轴的下标：mid = left + (right - left) / 2
（1）如果nums[left] < nums[right]：说明没有旋转，直接返回0。
（2）如果nums[mid] > nums[mid + 1]：说明nums[mid+1]是轴，直接返回mid+1。
（3）如果nums[mid] > nums[0]：说明nums[mid]在轴的前面，继续往后找，left = mid + 1。
（4）如果nums[mid] <= nums[0]：说明nums[mid]在轴的后面，则继续往前找，right = mid - 1。
（5）如果left > right，直接返回0。
3.如果rotate_index==0，说明数组没有旋转，直接在整个数组二分查找。
4.如果target > nums[0]：说明target在轴的前面，在0~rotate_index之间二分查找。
4.如果target <= nums[0]：说明target在轴的后面，在rotate_index~nums.size()-1之间二分查找。

3.代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()){
            return -1;
        }
        if(nums.size() == 1){
            return target == nums[0] ? 0 : -1;
        }
        int rotate_index = find_rotate_index(nums,0,nums.size() - 1);
        if(nums[rotate_index] == target){
            return rotate_index;
        }
        else if(rotate_index == 0){//没有旋转，直接对数组进行二分查找
            return binary_search(nums,0,nums.size() - 1, target);
        }
        else if(target < nums[0]){//从旋转轴右边找
            return binary_search(nums,rotate_index,nums.size() - 1,target);
        }
        //如果target >= nums[0],则肯定在旋转轴左边
        return binary_search(nums,0,rotate_index,target);
    }
    int binary_search(vector<int>& nums,int left, int right, int target){
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return -1;
    }
    int find_rotate_index(vector<int>& nums, int left,int right){
        if(nums[left] < nums[right]){
            return 0;
        }
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1]){//说明是旋转轴的前一个元素
                return mid + 1;
            }
            else {
                if(nums[mid] < nums[left]){//说明mid是后面部分
                    right = mid - 1;
                }
                else{ //说明mid在前面部分
                    left = mid + 1;
                }
            }
        }
        return 0;
    }
};

4.复杂度分析

时间复杂度：O(logn)
空间复杂度：O(1)