假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點上進行了旋轉(zhuǎn)。
( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
搜索一個給定的目標值，如果數(shù)組中存在這個目標值，則返回它的索引，否則返回 -1 。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
你的算法時間復(fù)雜度必須是 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

• show the code:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l,r = 0,len(nums)-1
        while l < r:
            m = (l+r)//2
            if nums[l] <= nums[m] and nums[l]<=target<=nums[m]:
                r = m
            elif nums[l] > nums[m] and target>=nums[l]>nums[m]:
                r = m
            elif nums[l] > nums[m] and target<=nums[m]<nums[l]:
                r = m
            else:
                l = m+1
        return l if nums[l]==target else -1

• 此題還比較難，我之前面小米時也被問到過，當(dāng)時把所有情況都列了出來，其實現(xiàn)在看來是不能AC的。
• 首先題目要求log(n)的復(fù)雜度，所以一定是用二分法。其次關(guān)鍵點是要找出所有需要在前半段找的情況，總共只有三種：

1.nums[0] <= nums[mid],（0-mid不包含旋轉(zhuǎn)）且nums[0] <= target <= nums[mid]時high向前規(guī)約；
2.nums[mid] < nums[0]（0-mid包含旋轉(zhuǎn)），target <= nums[mid] < nums[0]時向前規(guī)約（target在旋轉(zhuǎn)位置到mid之間）
3.nums[mid] < nums[0]，nums[mid] < nums[0] <= target時向前規(guī)約（target在0到旋轉(zhuǎn)位置之間）

• 我們只需要考慮比較三個數(shù)：第一個數(shù)，中間的數(shù)和target即可確定我們要不要在前半段找。
• 如果前半段沒有旋轉(zhuǎn)，而且目標值在第一個數(shù)和中間數(shù)之間，那么肯定在前半段。
• 如果前半段有旋轉(zhuǎn)，說明旋轉(zhuǎn)位置在前半段。而目標值在旋轉(zhuǎn)位置到中間數(shù)之間，也在前半段中尋找。如果目標值在第一個數(shù)到旋轉(zhuǎn)位置之間，則也在前半段中找，也就是說：如果目標值處于(mid,left)區(qū)間之外，我們都需要在前半段中尋找。
• 找出在前半段中尋找的所有條件，其他條件就是在后半段中尋找，注意后半段中尋找時，不要包括中間數(shù)，不然會陷入死循環(huán)—考慮nums=[4,5],target=4，具體表現(xiàn)為l = m+1。
• 由于每次縮小一半的查找范圍，時間復(fù)雜度可以達到log(n)，空間復(fù)雜度為1。