📘 題目敘述
給定一個已排序的整數陣列 nums 與一個整數 target，請在陣列中搜尋 target，若存在則回傳其索引，否則回傳 -1。
你必須使用時間複雜度為 O(log n) 的演算法。
條件限制
1 ≤ nums.length ≤ 10^4-10^4 ≤ nums[i], target ≤ 10^4nums為遞增排序（ascending order）nums中的元素皆不重複
🧠 解題思路
我的做法是使用 Binary Search（二分搜尋）。
因為陣列已經排序過，每次比較中間的元素後，都可以直接捨棄一半不可能包含答案的區間。
所有變數（對應程式碼）
n：陣列nums的長度left：目前搜尋區間的左邊界right：目前搜尋區間的右邊界pos：目前區間的中間位置索引
while (left <= right)：只要區間還存在就繼續搜尋
這個迴圈代表：
[left, right]是目前可能包含 target 的搜尋區間- 只要
left <= right，區間內至少還有一個元素需要檢查
每一輪迴圈實際在做的事情
在 while (left <= right) 的每一輪中，我都會針對目前的搜尋區間 [left, right] 做一次判斷與縮小。
第一步：計算中間位置
int pos = (left + right) / 2;
這一行會取得目前搜尋區間的中間索引 pos。
接下來會根據 nums[pos] 與 target 的比較結果，決定要往左半邊或右半邊繼續搜尋。
第二步：比較中間值與 target
接下來會根據比較結果，出現以下三種情況：
情況一：nums[pos] == target
if (nums[pos] == target) {
return pos;
}
中間位置的元素剛好等於 target，代表已經找到答案，直接回傳索引 pos。
情況二：nums[pos] < target（目標在右半邊）
else if (nums[pos] < target) {
left = pos + 1;
}
因為陣列是遞增排序，中間值小於 target，pos 與其左側元素皆不可能是答案。
搜尋區間縮小為 [pos + 1, right]。
情況三：nums[pos] > target（目標在左半邊）
else {
right = pos - 1;
}
中間值大於 target，pos 與其右側元素皆不可能是答案。
搜尋區間縮小為 [left, pos - 1]。
第三步：更新搜尋區間並進入下一輪
根據上述三種情況之一，更新 left 或 right，回到 while 條件，判斷是否還有區間需要搜尋。
迴圈結束後
- 當
left > right時，代表搜尋區間已經為空 - 所有可能的位置都已經被檢查過
- 若仍未找到
target，回傳-1
💻 程式碼實作
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int pos = (left + right) / 2;
if (nums[pos] == target) {
return pos;
} else if (nums[pos] < target) {
left = pos + 1;
} else {
right = pos - 1;
}
}
return -1;
}
};