題目解釋
有一個按 ascending sorted 的整數 array nums（每個值都是 unique 的）。
nums 可能會在未知的 pivot index k (1 <= k < nums.length) 處進行旋轉，
使得結果數組為 [nums[k], nums[k+1], ... , nums[n-1], nums[0], nums[1], ..., nums[k-1]] （從 0 開始）。
例如，[0, 1, 2, 4, 5, 6, 7] 可能會在 pivot index 3 處旋轉並變為 [4, 5, 6, 7, 0, 1, 2]。
給定可能旋轉後的陣列 nums 和整數 target，如果目標在 nums 中，則傳回 target 的 index，如果不在 nums 中，則傳回 -1。
您必須編寫一個在 O(log n) 時間內執行的演算法。
範例
- 輸入:
nums = [4, 5, 6, 7, 0, 1, 2], target = 0 - 輸出:
4
目標 0 在 nums 的第 4 個位置。
最佳解法
看到
O(log n)就要反射性的想到二元搜尋法 (Binary Search)！
這題跟 153. Find Minimum in Rotated Sorted Array 真的很像。
但是我自己就有一個疑問，就是為什麼在 153. Find Minimum in Rotated Sorted Array 用的邏輯到這題來卻會不正確。
明明他們同樣都是把 sorted array 給 pivot，
因此 array 裡面總是會有一部分是 sorted 的一部分是 unsorted 的，
只不過一個是找最小值一個是搜尋？
細探之後才了解這兩題運用到的性質其實不太一樣，
這題簡單來說邏輯就是先切左右兩邊（left ~ mid 與 mid ~ right)，
確認哪一邊是 sort 過的，
如果 target 的值在 sort 過的那一塊的範圍的話，
就在那邊繼續找，否則就找另一邊。
而 153. Find Minimum in Rotated Sorted Array 則是經過窮舉所有場景所 summarize 出來的經驗法則 (?)，
因為只關心最小值在哪。
步驟
- 先切左右兩邊
left~midmid~right
- 確認哪一邊是 sort 過的
- 如果 target 的值在 sort 過的那一塊的範圍的話
=> 在那邊繼續找 - 否則
=> 找另一邊
程式碼
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while (left <= right):
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
其實我覺得註解寫在旁邊好像比較好懂…給大家參考看看。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while (left <= right):
mid = left + (right - left) // 2
if nums[mid] == target: # mid == target
return mid
elif nums[left] <= nums[mid]: # left side is sorted
if nums[left] <= target < nums[mid]: # target in sorted left side
right = mid - 1 # shrink left side range
else:
left = mid + 1 # find another side (right)
else: # right side is sorted
if nums[mid] < target <= nums[right]: # target in sorted right side
left = mid + 1 # shrink right side range
else:
right = mid - 1 # find another side (left)
return -1
時間複雜度
O(logn)，n 是 nums 的元素個數。
空間複雜度
O(1)。
結語
好棒，python 可以直接寫 a < b < c 的形式，
查了一下才知道這種運算式的正確術語叫做「鏈式比較」(Chained Comparison)，
又是已知用火的一天🔥
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art
- [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26
