解題說明
Binary Search（二元搜尋）
題目描述：給定一個已排序的整數陣列 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 次比較即可找到答案。
C++ 解法
複雜度分析
時間複雜度：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有何差異，各自適用於什麼情境？ - 如何將二元搜尋應用於「在旋轉排序陣列中搜尋」（LeetCode 33）這類變形題目？