算法模板（二分法开区间模板，二分法闭区间模板）

二分法闭区间模板：

class Solution {// lower_bound 返回最小的满足 nums[i] >= target 的 i// 如果数组为空，或者所有数都 < target，则返回 nums.size()// 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]// 闭区间写法int lower_bound(vector<int>& nums, int target) {int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空// 循环不变量：// nums[left-1] < target// nums[right+1] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right]} else {right = mid - 1; // 范围缩小到 [left, mid-1]}}return left;}

二分法开区间模板：

// 开区间写法int lower_bound3(vector<int>& nums, int target) {int left = -1, right = nums.size(); // 开区间 (left, right)while (left + 1 < right) { // 区间不为空// 循环不变量：// nums[left] < target// nums[right] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid; // 范围缩小到 (mid, right)} else {right = mid; // 范围缩小到 (left, mid)}}return right;}

二分法左闭右开区间写法：

// 左闭右开区间写法int lower_bound2(vector<int>& nums, int target) {int left = 0, right = nums.size(); // 左闭右开区间 [left, right)while (left < right) { // 区间不为空// 循环不变量：// nums[left-1] < target// nums[right] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right)} else {right = mid; // 范围缩小到 [left, mid)}}return left;}

视频链接：二分查找为什么总是写错？_哔哩哔哩_bilibili

来源：35. 搜索插入位置 - 力扣（LeetCode）