704. Binary Search

Binary Search（二元搜尋）

題目描述：給定一個已排序的整數陣列 nums 和一個目標值 target，請回傳 target 在陣列中的索引。若不存在，則回傳 -1。

解題思路：由於陣列已排序，我們可以利用二元搜尋（Binary Search）大幅降低搜尋時間。核心概念是每次將搜尋範圍縮減一半：

1. 設定左指標 left = 0，右指標 right = n - 1，代表目前搜尋區間為 [left, right]。
2. 每次計算中間位置 mid = left + (right - left) / 2（避免整數溢位）。
3. 比較 nums[mid] 與 target：
   • 若 nums[mid] == target，找到目標，回傳 mid。
   • 若 nums[mid] < target，目標在右半部，令 left = mid + 1。
   • 若 nums[mid] > target，目標在左半部，令 right = mid - 1。
4. 當 left > right 時，區間為空，目標不存在，回傳 -1。

二元搜尋的關鍵在於每次都能排除一半的可能性，因此即使陣列有 10 億個元素，最多只需約 30 次比較即可找到答案。

時間複雜度：O(log n) — 每次迭代將搜尋區間縮減為一半，因此最多需要 log₂(n) 次比較。

空間複雜度：O(1) — 只使用了 left、right、mid 三個整數變數，不依賴輸入大小的額外空間。

線性搜尋 O(n)：從頭到尾逐一比較每個元素，直到找到目標。實作最簡單，但效率遠低於二元搜尋，不適合大型已排序陣列。

遞迴二元搜尋 O(log n)：以遞迴方式實作二元搜尋，每次呼叫傳入縮減後的左右邊界。邏輯與迭代版本完全相同，但每次遞迴呼叫會使用 O(log n) 的呼叫堆疊空間，空間效率略遜於迭代版本。

1. 若陣列中存在重複元素，如何找到目標值的最左邊（或最右邊）出現位置？
2. 二元搜尋的邊界條件 left <= right 與 left < right 有何差異，各自適用於什麼情境？
3. 如何將二元搜尋應用於「在旋轉排序陣列中搜尋」（LeetCode 33）這類變形題目？