最基礎的 binary search，是在已排序的陣列中搜尋指定的 target。因為每次都能排除一半的搜尋範圍，所以時間複雜度是 O(log n)，下面是最常見的寫法：
int binarySearch(vector<int>& nums, int target) {
int left=0, right=nums.size()-1;
while (left <= right) {
int mid = left+(right-left)/2;
if (target < nums[mid]) right = mid - 1;
else if (target > nums[mid]) left = mid + 1;
else return mid;
}
return -1;
}
其中 mid=left+(right-left)/2 不能寫成 mid=(left+right)/2 是為了避免 left+right 超過 int 範圍而 overflow。
這個版本的目標很單純：找到 target 就直接回傳 index，找不到就回傳 -1，但真正容易混亂的地方，通常出現在各種變形題，例如：
- 找不到時，要回傳小於 target 的最大值位置
- 陣列中有重複值時，要回傳最左邊或最右邊的 index
- 答案不是某個值，而是某個符合條件的邊界
這時候就很容易開始糾結，while 到底要寫 < 還是 <=？最後要回傳 left 還是 right？更新邊界時要不要寫成 mid-1 或 mid+1？
通用模板
如果題目不是要找單一的 target，而是要找到某個邊界，思考方式就要換成：用一個條件判斷答案在哪一側，然後每次排除一半的搜尋空間。常見的邊界像是回傳 >= target 的最小 index。
找邊界時，通常不會在 nums[mid] == target 的瞬間就回傳，因為 mid 可能只是其中一個答案，不一定是最左或最右的邊界。我們會讓搜尋範圍持續縮小，直到 left == right，此時該位置就是最後留下來的邊界。
而可能成為答案的 mid 不能隨便被排除，要把它留在搜尋範圍內，根據題目類型會有以下兩個常用模板。
找最左邊符合條件的
假設條件分布是：false, false, false, true, true，我們要找第一個 true：
// 找最左邊符合條件的 index
while (left < right) {
int mid = left + (right - left) / 2;
if (...) right = mid;
else left = mid + 1;
}
return left;
例如要找 >= target 的最小 index，可以把 if 條件寫成 nums[mid] >= target，當 if 成立時，代表答案可能就是 mid，也可能還在更左邊，所以更新成 right = mid。
找最右邊符合條件的
這類的條件分布會是 true, true, true, false, false，我們要找最後一個 true：
// 找最右邊符合條件的 index
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (...) left = mid;
else right = mid - 1;
}
return left;
例如要找 <= target 的最大 index，可以把條件寫成 nums[mid] <= target，當 if 成立時，代表答案可能就是 mid，也可能還在更右邊，所以更新成 left = mid。
為了避免無窮迴圈，要注意 mid 的位子：如果更新時寫 right=mid，中點要偏左，也就是 (right-left)/2；如果更新時寫 left=mid，中點要偏右，也就是 (right-left+1)/2。
簡單記法：保留哪一邊的 mid，中點就要往另一邊偏。
LeetCode 練習題目
找到 target 就回傳
704. Binary Search：最基礎的 binary search，找到就回傳 index，找不到回傳 -1。
33. Search in Rotated Sorted Array：雖然陣列被旋轉過，但每次仍然至少有一半是排序好的。先判斷哪一半有序，再判斷 target 是否落在那一半。
找邊界：簡單版
35. Search Insert Position：標準的 lower bound，也就是找 >= target 的最小 index。需要特別注意如果 target 比所有數字都大，答案會是 nums.size()。
34. Find First and Last Position of Element in Sorted Array：可以拆成兩個邊界來看，先找第一個 >= target 的位置，再找最後一個 <= target 的位置，最後確認這兩個位置是否真的等於 target。
875. Koko Eating Bananas：也是找第一個符合的 index。
找邊界：變化版
153. Find Minimum in Rotated Sorted Array：透過 nums[mid] 和右邊界比較，判斷最小值在左半邊還是右半邊。
162. Find Peak Element：透過比較 nums[mid] 和 nums[mid + 1]，判斷峰值會出現在左半邊還是右半邊。
