Meta 面試注重演算法變體和邊界處理。本文通過局部最小值問題，展示二分搜尋的靈活應用，oavoservice 助你掌握二分搜尋的精髓。
📋 題目描述
給定一個無序陣列，找到任意一個局部最小值的索引。
定義： arr[i] 是局部最小值，如果 arr[i] < arr[i-1] 且 arr[i] < arr[i+1]。邊界元素只需要小於相鄰元素。
範例：
Input: [9, 6, 2, 14, 5, 7, 4]
Output: 2 (arr[2] = 2)
🎯 核心考點
- 二分搜尋變體 - 非單調陣列的二分
- 邊界處理 - 陣列邊界的特殊情況
- 時間複雜度 - O(log n) 解法
- 正確性證明 - 為什麼二分有效
💡 解題思路（oavoservice 指導）
方法：二分搜尋
def find_local_minimum(arr):
n = len(arr)
if n == 1: return 0
if arr[0] < arr[1]: return 0
if arr[n-1] < arr[n-2]: return n - 1
left, right = 1, n - 2
while left <= right:
mid = (left + right) // 2
if arr[mid] < arr[mid-1] and arr[mid] < arr[mid+1]:
return mid
if arr[mid] > arr[mid-1]:
right = mid - 1
else:
left = mid + 1
return -1
時間複雜度： O(log n) 空間複雜度： O(1)
🚀 關鍵洞察
為什麼二分有效？
如果 arr[mid] > arr[mid-1]，左側必有局部最小值。
如果 arr[mid] > arr[mid+1]，右側必有局部最小值。
每次都能排除一半的搜尋空間。
💼 oavoservice 助力
演算法變體 - 掌握二分搜尋的各種應用 正確性證明 - 清晰解釋演算法原理 邊界處理 - 完善的邊界條件 程式碼優化 - 簡潔高效的實作
聯繫 oavoservice，專業 VO 面試輔助！
標籤： #Meta #二分搜尋 #演算法變體 #VO輔助 #面試輔助 #一畝三分地
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。