Binary Search Template

模板

左閉右開

• 選擇 [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()：

  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()：

  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 的數
  }