題目描述:給定一個已排序的整數陣列 nums 和一個目標值 target,請回傳 target 在陣列中的索引。若不存在,則回傳 -1。
解題思路:由於陣列已排序,我們可以利用二元搜尋(Binary Search)大幅降低搜尋時間。核心概念是每次將搜尋範圍縮減一半:
left = 0,右指標 right = n - 1,代表目前搜尋區間為 [left, right]。mid = left + (right - left) / 2(避免整數溢位)。nums[mid] 與 target:
nums[mid] == target,找到目標,回傳 mid。nums[mid] < target,目標在右半部,令 left = mid + 1。nums[mid] > target,目標在左半部,令 right = mid - 1。left > right 時,區間為空,目標不存在,回傳 -1。二元搜尋的關鍵在於每次都能排除一半的可能性,因此即使陣列有 10 億個元素,最多只需約 30 次比較即可找到答案。
時間複雜度:O(log n) — 每次迭代將搜尋區間縮減為一半,因此最多需要 log₂(n) 次比較。
空間複雜度:O(1) — 只使用了 left、right、mid 三個整數變數,不依賴輸入大小的額外空間。
1. Set left = 0, right = len(nums) - 1 2. While left <= right: a. Compute mid = left + (right - left) / 2 b. If nums[mid] == target: return mid c. If nums[mid] < target: set left = mid + 1 d. Else: set right = mid - 1 3. Return -1 (target not found)
線性搜尋 O(n):從頭到尾逐一比較每個元素,直到找到目標。實作最簡單,但效率遠低於二元搜尋,不適合大型已排序陣列。
遞迴二元搜尋 O(log n):以遞迴方式實作二元搜尋,每次呼叫傳入縮減後的左右邊界。邏輯與迭代版本完全相同,但每次遞迴呼叫會使用 O(log n) 的呼叫堆疊空間,空間效率略遜於迭代版本。
left <= right 與 left < right 有何差異,各自適用於什麼情境?