33. 搜索旋轉排序陣列
題目來源：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
題目
假設按照升序排序的陣列在預先未知的某個點上進行了旋轉，
( 例如，陣列 [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. 搜索旋轉排序陣列》問題的主要內容，
歡迎關注微信公眾號《書所集錄》
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/153391.html
標籤：Python