題目：

整數數組nums按升序排列，數組中的值互不相同

在傳遞給函數之前，nums在預先未知的某個小標K上進行了旋轉，使數組變為[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]，小標從0開始計數。例如[0,1,2,4,5,6,7]?在下標?3?處經旋轉后可能變為?[4,5,6,7,0,1,2]?。

給定旋轉后的數組nums和一個整數target,如果nums中存在這個目標值target，則返回它的小標，否則返回-1

---

方法一：二分查找

對于有序數組，可以使用二分查找的方法查找元素

這道題中，數組本身不是有序的，進行旋轉后只保證了數組的局部是有序的

可以發現，將數組從中間分開成左右兩部分，一定有一部分的數組是有序的，拿示例看，從?6?這個位置分開以后數組變成了?[4, 5, 6]?和?[7, 0, 1, 2]?兩個部分，其中左邊?[4, 5, 6]?這個部分的數組是有序的，其他也是如此。

這啟示我們，可以在常規二分查找的時候查看當前mid為分割位置分割出來的兩個部分[l, mid]?和?[mid + 1, r]哪個部分是有序的，并根據有序的那個部分確定該如何改變二分查找的上下界，因為可以根據有序的部分判斷出target在不在這個部分。

如果?[l, mid - 1]?是有序數組，且?target?的大小滿足?[nums[l],nums[mid])，應該將搜索范圍縮小至?[l, mid - 1]，否則在?[mid + 1, r]?中尋找

如果 [mid, r] 是有序數組，且 target 的大小滿足 (nums[mid+1],nums[r]]，則我們應該將搜索范圍縮小至 [mid + 1, r]，否則在 [l, mid - 1] 中尋找。

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""if not nums:  #如果輸入數組為空，直接返回-1表示未找到return -1l,r=0,len(nums)-1  #初始化兩個指針l(left)和r(right)，分別指向數組的開始和結束位置while l<=r: #開始二分查找循環，當左指針不超過右指針時繼續循環mid=(l+r)//2  #計算中間位置midif nums[mid]==target: #如果中間值正好等于目標值，直接返回中間索引return midif nums[0]<=nums[mid]:#檢查數組的左半部分是否有序（旋轉點在mid右側）if nums[0]<=target<nums[mid]: #如果目標值在有序的左半部分范圍內，將右指針移到mid左側r=mid-1else:l=mid+1  #否則目標值在右半部分，將左指針移到mid右側else: #如果左半部分無序（旋轉點在mid左側），則右半部分必定有序if nums[mid]<target<=nums[len(nums)-1]:#如果目標值在有序的右半部分范圍內，將左指針移到mid右側l=mid+1else:    #否則目標值在左半部分，將右指針移到mid左側r=mid-1return -1

時間復雜度：O(logn)，其中?n?為?nums?數組的大小。整個算法時間復雜度即為二分查找的時間復雜度?O(logn)

空間復雜度：?O(1)

源自力扣官方題解
?