33. 搜尋旋轉排序數組
題目
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。
搜尋一個給定的目标值，如果數組中存在這個目标值，則傳回它的索引，否則傳回 -1 。
你可以假設數組中不存在重複的元素。
你的算法時間複雜度必須是 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
解題思路
思路：二分查找
題目中，要求算法時間複雜度必須是 O(log n) 級别，在這裡，其實提示可以使用二分查找的方法。
有個地方需要注意的是，二分查找，要求的是清單的元素必須是有序的。在這裡，雖然原始數組是按照升序排序的，但數組在某個未知的點進行旋轉之後，清單隻有局部才是有序的。
但其實這裡并不會沖突，因為将經過旋轉的清單分割成兩部分時，一定有一個部分是有序的。
直接以上面的示例 1 為例，[4, 5, 6, 7, 0, 1, 2]，如果将數組分割成 [4, 5, 6] 和 [7, 0, 1, 2]，那麼前面 [4, 5, 6] 這部分是有序的。這在其他符合這些條件的數組一樣是成立的。
上面提到數組分為兩部分，那麼可以考慮從在中點的位置進行劃分，将原數組劃分為 [left, mid] 和 [mid + 1, right] 兩部分。
當将旋轉後的數組分成上述兩部分時，現在要考慮的就是 target 值，會落在哪個區間？當 target 值落在有序那部分的區間中，這個比較好了解，這個時候上下邊界是确定的，題目中也說明【可以假設數組中不存在重複的元素。】，那麼有且隻有一個元素與之比對。
現在具體分析判斷 target 會落在哪個區間：
如果 [left, mid - 1] 這部分是有序的，且 target 落在 [nums[left], nums[mid]) 這個區間，那麼就可以将搜尋的範圍縮小到 [left, mid - 1]，否則的話，将在 [mid + 1, right] 這個區間中進行搜尋；
如果 [mid, right] 這部分是有序的，且 target 落在 (nums[mid+1], nums[right]]，那麼就在 [mid + 1, right] 這個區間進行搜尋，否則在 [left, mid - 1] 這個區間進行搜尋。
下面是具體的代碼實作。
代碼實作
class Solution:
def search(self, nums: List[int], target: int) -> int:
# nums 為空時，直接傳回 -1
if not nums:
return -1
# 初始左右邊界
left, right = 0, len(nums) - 1
# 判斷哪部分區間是有序的
# 判斷 target 會落在哪個區間
while left <= right:
# 數組劃分為兩部分
mid = (left + right) // 2
# 如果目标值與劃分區間的元素相等時，直接傳回
if nums[mid] == target:
return mid
# 判斷區間是否有序
# 這裡表示 [left, mid - 1] 是有序的
if nums[0] <= nums[mid]:
# target 落在 [left, mid - 1] 這個區間
if nums[0] <= target < nums[mid]:
# 重新劃分右邊界
right = mid - 1
# target 落在 [mid + 1, right] 這個區間
else:
# 重新劃分左邊界
left = mid + 1
# nums[0] > nums[mid] 時，表示 [mid + 1, right] 有序
else:
# target 落在 [mid + 1, right] 時
if nums[mid] < target <= nums[right]:
# 重新劃分左邊界
left = mid + 1
else:
# target 落在 [left, mid - 1] 這個區間
# 重新劃分左邊界
right = mid - 1
return -1
實作結果
以上就是使用二分查找的思想，解決《33. 搜尋旋轉排序數組》問題的主要内容。
歡迎關注微信公衆号《書所集錄》