今天解的題目是第三十三題 Search in Rotated Sorted Array，這題要求我們在一個可能被旋轉過的升冪排序陣列中，找出目標數字 target 的索引位置，若不存在則回傳 -1。這題的關鍵在於理解旋轉後的陣列結構，例如 [4,5,6,7,0,1,2] 是由兩段遞增序列組成的。程式的第一步是先找到旋轉點，也就是最小值的位置。這可以透過比較中間值 nums[m] 和右邊界 nums[r] 來判斷，若 nums[m] > nums[r]，代表最小值在右邊，否則在左邊，最後當左右指標重合時就能找到旋轉點。接著根據 target 的值判斷要在旋轉點的左邊或右邊區間進行搜尋。最後再進行標準的二分搜尋，若找到目標則回傳索引，否則回傳 -1。
iThome鐵人賽
看影片追技術