模板

左閉右開

選擇 [left, right) 左閉右開的原因 : 因為 while 判斷式為 left < right, 當跳出迴圈時, left == right, 不用考慮說是要返回 left 還是 right, 因為兩者相等
g(x) 為一 function, 找到一元素 m 滿足：
- x ≥ m 時, g(x) > 0, 也就是 g(x) = true
- x < m 時, g(x) ≤ 0, 也就是 g(x) = false
➔ 這樣做的用意是：找到一個臨界點 m, 能使區間 [m, ∞) 中的任意元素 x 皆滿足 g(x) > 0
且區間 (-∞, m) 中的任意元素 x 皆滿足 g(x) ≤ 0
簡易模板：704. Binary Search
除非是特殊情況, 不然不要在 while 中做任何 return 的動作, 這樣做很有可能導致出錯
為何 while 判斷式為 left < right ? 這種時候「考慮 edge case」就對了

e.g. nums = [1], target = 1

➔ g(x) = nums[mid] ≥ 1, 目標是找到第一個 idx i 使得 nums[i] ≥ 1 成立
- left = 0, right = 1 ➔ mid = 0, nums[mid] = 1
  ➔ 因為 1 ≥ 1 成立, 所以 g(1) = true ➔ right = mid = 0
- left = 0, right = 0, 跳出迴圈 ➔ 從位置 0 的元素開始 ≥ 1
- 返回 left
左閉右開的缺點：right 容易 overflow, 像是 69. Sqrt(x)、278. First Bad Version

左閉右閉（我都用這個）

簡易模板：
最後 left 會是第一個滿足 g(x) = true 的元素
使用時機：if 判斷式需要存取到 idx = right 的元素
範例 : 33. Search in Rotated Sorted Array 由於需要判斷 nums[right] 故不適合用左閉右開

範例

實現 lowerBound()：

cpp

int lowerBound(const vector<int>& nums, const int target)
{
    const int n = nums.size();
    int left = 0, right = n - 1;

    while (left <= right) {
        const int mid = left + (right - left) / 2;

        // mid 右側元素皆 ≥ target, 故往左邊縮小區間
        if (nums[mid] >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return left; // left 為第一個 ≥ target 的數
}

實現 upperBound()：

cpp

int upperBound(const vector<int>& nums, const int target)
{
    const int n = nums.size();
    int left = 0, right = n - 1;

    while (left <= right) {
        const int mid = left + (right - left) / 2;

        // mid 右側元素皆 > target, 故往左邊縮小區間
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return left; // left 為第一個 > target 的數
}