C++如何实现二分查找的左闭右开区间逻辑模板-C++-PHP中文网

左闭右开区间更不容易越界，因为right始终指向搜索范围之外的位置，循环条件为left

为什么左闭右开区间比左闭右闭更不容易越界

因为 right 始终指向「搜索范围之外」的位置，循环条件用 left 天然规避了 <code>left == right 时的边界判断混乱；每次缩小区间时，mid 落在 [left, right) 内，right = mid 或 left = mid + 1 都能保证不漏、不越、不卡死。

标准左闭右开二分模板（查找第一个 ≥ target 的位置）

这是最常用、最稳定的起点。返回的是插入位置，即满足 nums[i] >= target 的最小下标；若不存在，返回 nums.size()。
int lower_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left <p>关键点：</p>
<ul>
<li>
<code>right</code> 初始化为 <code>nums.size()</code>，不是 <code>nums.size() - 1</code>
</li>
<li>
<code>mid</code> 计算用 <code>left + (right - left) / 2</code>，防溢出</li>
<li><code>nums[mid]  → <code>left = mid + 1</code>（跳过 <code>mid</code>，因它肯定不满足）</code></li>
<li>
<code>else</code> → <code>right = mid</code>（<code>mid</code> 可能是答案，不能跳过）</li>
</ul>
<h3>怎么改写成查找最后一个 ≤ target 的位置</h3>
<p>本质是把判定逻辑翻过来，并调整收缩方向。返回最大下标 <code>i</code> 满足 <code>nums[i] ；不存在则返回 <code>-1</code>。</code></p>
<pre class="brush:php;toolbar:false;">int upper_bound_exclusive(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left  target 的位置，前一个是最后一个 ≤ target
}</int>
注意：

C++ Code Review Master
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

判定条件是 nums[mid] ，成立就往右找更大合法值 → <code>left = mid + 1

最终 left 是第一个不满足条件的位置，所以答案是 left - 1

调用前需检查 left == 0，此时 left - 1 为 -1，表示无解

常见错误：混淆 mid 更新和区间语义

最容易错的是在 else 分支写成 right = mid - 1 —— 这直接破坏左闭右开前提，因为 mid 本就在当前有效范围内（[left, right)），而 right = mid - 1 会把 mid - 1 排除在外，但 mid 本身可能就是答案。

另一个坑是初始化 right = nums.size() - 1 后还用 left 条件 —— 此时区间变成 <code>[left, right]，但代码逻辑没同步改，必然漏判或越界。

真正要记住的只有两条铁律：

只要用左闭右开，right 就必须初始化为「上界」（如数组长度、指针末端），不是「最后一个索引」

所有赋值操作都必须与区间定义一致：right = mid 表示新右界是 mid（不包含），left = mid + 1 表示新左界从 mid + 1 开始（包含）

模板不难记，但每次写都要默念一遍区间含义——多数 bug 都出在“以为自己懂了，其实没想清楚 right 到底代表什么”。