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

左闭右开区间更不易出错，因为right作为“第一个不合法位置”，天然规避mid+1越界风险，终止条件统一为left==right，初始化需设right=vec.size()而非size()-1，且mid=left+(right-left)/2防溢出。

c++如何实现二分查找的左闭右开区间逻辑

为什么左闭右开区间比左闭右闭更不容易出错

因为 end 作为“第一个不合法位置”，天然规避了 mid + 1 越界风险，且循环终止条件统一为 left == right，不用额外处理边界收缩后的越界判断。

常见错误是把 right 初始化成 size() - 1（这是左闭右闭的写法），结果在 right = mid 时漏掉元素，或在 left = mid + 1 时超出范围。

left 初始值必须是 0，right 初始值必须是 vec.size()（不是 vec.size() - 1）
循环条件固定用 left ，不是 <code>left
更新逻辑中，right = mid（不是 mid - 1），因为 mid 本身可能非法，right 是开区间端点
返回值直接用 left，它就是插入位置或目标下标，无需再校验

标准模板：查找第一个 ≥ target 的位置（lower_bound）

这是左闭右开区间最典型的用法，也是 STL 中 std::lower_bound 的行为。它天然支持“不存在时返回插入位置”这一语义。

int lower_bound(const vector<int>& vec, int target) {
    int left = 0, right = vec.size();
    while (left <p>注意：<code>vec[mid]  时才移动 <code>left</code>，否则收缩 <code>right</code> —— 这保证了最终 <code>left</code> 指向第一个满足 <code>vec[i] >= target</code> 的位置。</code></p>
<p>如果数组为空，<code>vec.size() == 0</code>，<code>right</code> 为 0，循环不执行，直接返回 0，符合预期。</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master"><img
														src="https://img.php.cn/upload/skill/000/000/081/179051228971575.jpg" alt="C++ Code Review Master" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="overflowclass">C++ Code Review Master</a>
													<p class="overflowclass">组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>
<h3>如何改造成查找第一个 > target 的位置（upper_bound）</h3>
<p>只需把判断条件从 <code> 改成 <code>，其余结构完全不变。这说明左闭右开模板的可迁移性很强。</code></code></p>
<ul>
<li>原 <code>lower_bound</code> 是找 ≥，对应条件是 <code>vec[mid] </code>
</li>
<li>改 <code>upper_bound</code> 是找 >，对应条件变成 <code>vec[mid] </code>
</li>
<li>仍用 <code>left = mid + 1</code> 和 <code>right = mid</code>，逻辑一致性高，不易混淆</li>
</ul>
<p>示例：</p>
<pre class="brush:php;toolbar:false;">int upper_bound(const vector<int>& vec, int target) {
    int left = 0, right = vec.size();
    while (left <h3>容易被忽略的整型溢出与性能细节</h3>
<p><code>mid = left + (right - left) / 2</code> 是必须的写法，不能写成 <code>(left + right) / 2</code> —— 后者在 <code>left</code> 和 <code>right</code> 都接近 <code>INT_MAX</code> 时会整型溢出。</p>
<p>另外，若数据量极大（比如上亿元素），除法本身虽快，但现代 CPU 对 <code>right - left</code> 做位运算优化有限；不过实际中几乎不会成为瓶颈，优先保证逻辑正确性。</p>
<p>真正容易踩坑的是：传入的 <code>vector</code> 是空的、<code>target</code> 比所有元素都大、或比所有元素都小 —— 这些情况在左闭右开模板里全部由 <code>left</code> 的终值自然覆盖，不需要额外 <code>if</code> 判断。</p></int>

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！