二分模板

// 查找 x 以及 x 的后继，即 >= 5
// [1,2,3,4,(5),5,5,5,5,6,7]
int l = 0, r = n; // 左闭右开
while (l < r) {
  int mid = (l + r) >> 1;
  if (nums[mid] >= target) {
    r = mid;
  } else {
    l = mid + 1;
  }
}
return nums[l];

// 查找 x 以及 x 的前驱，即 <= 5
// [1,2,3,4,5,5,5,5,(5),6,7]
int l = 0, r = n;
while (l < r) {
  int mid = (l + r + 1) >> 1;
  if (nums[mid] <= target) {
    l = mid;
  } else {
    r = mid - 1;
  }
}
return nums[l];

lower_bound, upper_bound

// [1,2,3,4,5,5,5,5,5,6,7]
// [1,2,3,4,(5),5,5,5,5,6,7] 下界，闭 >= 5
std::lower_bound(nums.begin(), nums.end(), 5);
std::lower_bound(nums.begin(), nums.end(), 5, [] (int element, int target) {
  return element < target;
}); // cmp 统一为 less，这里为第一个 !cmp 的元素

// [1,2,3,4,5,5,5,5,5,(6),7] 上界，开 > 5
std::upper_bound(nums.begin(), nums.end(), 5)
std::upper_bound(nums.begin(), nums.end(), 5, [] (int target, int element) {
  return target < element;
}); // cmp 统一为 less，这里为第一个 cmp 的元素

// C++20 ranges
// 当比较元素和目标元素对等时，基本同 std::upper_bound
std::ranges::upper_bound(nums, 5, less<>());
std::ranges::lower_bound(nums, 5, less<>());
// 当比较元素和目标元素不对等时，传参为 key_func
std::ranges::upper_bound(nums, 5, less<>(), key_func);
std::ranges::lower_bound(nums, 5, less<>(), key_func);