33. Search in Rotated Sorted Array

 

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

在这样一个数组中找到target，这个数组是递增序列的变体，如4 5 6 7 0 1 2，或5 6 7 0 1 2 3 4

解决方法，可以采用二分法思想：

------------------------------------------------------------------------------------------------------------------------------

假设数组是A，取左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回m；

（2）如果A[m]<A[r]（情况就类似于：如5 6 7 0 1 2 3 4中，m = 3,r = 7。A[3] = 0 < A[7] = 1）
    那么说明从m到r右半部分一定是有序的，此时只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。

（3）如果A[m]>=A[r]（情况就类似于：如4 5 6 7 0 1 2中，m = 3,r = 7。A[3] = 7 >= A[7] = 0）
     那么说明从l到m左半部分一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可

 -------------------------------------------------------------------------------------------------------------------------------

根据以上方法，每次可以切掉一半的数据，所以算法的时间复杂度是O(logn)，空间复杂度是O(1)。代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target){
        if(nums.capacity() == 0)  
            return -1;  
        int l = 0;    //左边缘
        int r = nums.capacity() - 1;  //右边缘
        while(l <= r){  
            int m = (l + r) / 2;  
            if(target == nums[m])  
                return m;  

            if(nums[m] < nums[r]){   //情况类似5 6 7 0 1 2 3 4（从中间到最后有序）
　　　　　　　　　if(target > nums[m] && target <= nums[r])   //这个数在右半部分
                    l = m + 1;  
                else  
                    r = m - 1;  
            }  
            else{                    //情况类似4 5 6 7 0 1 2（从左边缘到中间有序）
　　　　　　　　　　if(target >= nums[l] && target < nums[m])   //这个数在左半部分
                    r = m - 1;  
                else  
                    l = m + 1;                      
            }  
        }  
        return -1;  
    }  
};