Leetcode 33. Search in Rotated Sorted Array

Search in Rotated Sorted Array :

假設一個按升序排序的數組在的某個位置旋轉。

（[0,1,2,4,5,6,7]可能變成[4,5,6,7,0,1,2]）。

如果在數組中找到題目給的target值則返回它的索引，否則返回-1。

複雜度必須為O(log n)

Python

二分搜尋法求解 :

1. 如果target==A[m]，那麼m就是我們要的結果，直接返回

2. 如果nums[mid]<nums[right]，那麼說明從m到r一定是有序的（沒有受到rotate的影響），那麼我們只需要判斷target是不是在m到r之間，如果是則把左邊緣移到m+1，否則就target在另一半，即把右邊緣移到m-1。

3. 如果nums[mid]>=nums[right]，那麼說明從l到m一定是有序的，那麼我們只需要判斷target是不是在l到m之間，如果是則把右邊緣移到m-1，否則就target在另一半，即把左邊緣移到m+1。

時間複雜度: O(logN)

空間複雜度: O(1)

class Solution(object):
    def search(self, nums, target):
        if not nums : return -1
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)/2
            if nums[mid]==target:
                return mid
            if nums[mid]<nums[right]:
                if target>nums[mid] and target<=nums[right]:
                    left=mid+1
                else:
                    right=mid-1
            else:
                if target<nums[mid] and target>=nums[left]:
                    right=mid-1

                else:
                    left=mid+1
        return -1

C++

二分查找法，將數組一分為二，其中一個有序，另一個可能無序，對有序的部分作二分查找，循環下去。

class Solution {
public:
int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size()-1;
    while (l<=r) {
        int mid = (r-l)/2+l;
        if (nums[mid] == target)
            return mid;
        if (nums[mid] < nums[r]) {     //右伴有序
            if (nums[mid]<target && target<=nums[r])  
                l = mid+1;   //右伴二分查找
            else
                r = mid-1;   //右半段有序,但不在右半段的範圍內,因此對左半查找
        } else {   //左半段有序
            if(nums[l]<=target && target<nums[mid])
                r = mid-1;  //左伴二分查找
            else
                l = mid+1;  //左半段有序,但不在左半段的範圍內,因此對右半段查找
        }
    }
    return -1;
}
};