題目描述:給定一個山形陣列 arr(先嚴格遞增、到頂點後嚴格遞減),找到頂點的索引。保證頂點存在且唯一。
解題思路:利用二分搜尋縮小範圍。維護 lo = 0、hi = arr.size() - 1,取中點 mid,比較 arr[mid] 與 arr[mid + 1]:
arr[mid] < arr[mid + 1],代表目前在上升段,頂點在 mid 的右側,令 lo = mid + 1。arr[mid] > arr[mid + 1]),代表目前在下降段或已是頂點,頂點在 mid 或其左側,令 hi = mid。迴圈條件改為 lo < hi(不含等號),當 lo == hi 時即找到頂點索引。
時間複雜度:O(log n) — 每次迭代將搜尋範圍縮減一半,總共執行 O(log n) 次比較。
空間複雜度:O(1) — 只使用常數個指標變數,無需額外記憶體。
1. Initialize lo = 0, hi = len(arr) - 1
2. While lo < hi:
a. Compute mid = lo + (hi - lo) / 2
b. If arr[mid] < arr[mid + 1]:
- Peak is on the right: lo = mid + 1
c. Else:
- Peak is at mid or on the left: hi = mid
3. Return lo (lo == hi, the peak index)方法一:線性掃描
從索引 1 開始,找到第一個滿足 arr[i] > arr[i + 1] 的位置,該位置即為頂點。時間複雜度 O(n),空間複雜度 O(1)。對於小型輸入足夠,但題目要求 O(log n)。
方法二:max_element 標準庫函式
直接使用 std::max_element(arr.begin(), arr.end()) 找到最大值的迭代器,再轉為索引。實際上這是 O(n) 的線性掃描,並非真正的二分搜尋最佳解,但程式碼最短,適合快速驗證正確性。