leetcode 33. 搜尋旋轉排序數組  medium          

題目描述：

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。

搜尋一個給定的目标值，如果數組中存在這個目标值，則傳回它的索引，否則傳回 -1 。

你可以假設數組中不存在重複的元素。

你的算法時間複雜度必須是 O(log n) 級别。

解題思路：

數組元素不重複，是以可以先找到最小點，然後判斷target在哪個半邊，再進行二分查找

代碼：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty())
            return -1;
        
        int left=0,right=nums.size()-1;
        // 說明是個旋轉數組，先找最小點
        if(nums[0]>nums.back()){
            while(left<right){
                int mid=left+(right-left)/2;
                if(nums[mid]<=nums.back())
                    right=mid;
                else
                    left=mid+1;
            }
            
            // target在右半邊
            if(nums[left]<= target && target<=nums.back()){
                right=nums.size()-1;
            } else {
                left=0;
                right--;
            }
            
        }
        
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>=target)
                right=mid;
            else
                left=mid+1;
        }
        
        return  nums[left]==target?left:-1;
        
        
        
    }
};