C++如何实现二分查找算法寻找第一个小于目标值的元素-C++-PHP中文网

二分查找找第一个小于 target 的元素，本质是找右边界左侧位置；实际等价于 lower_bound 行为，即 l 最终停在第一个 ≥ target 的位置。

c++如何实现二分查找算法寻找第一个小于目标值的元素

二分查找找第一个小于 target 的元素，本质是找右边界左侧位置

直接说结论：这不是标准二分查找的常见变种，但可以复用 lower_bound 或手写逻辑——关键不是“小于”，而是“最后一个满足 arr[i] 的索引”。它等价于 <code>lower_bound 返回位置的前一个位置，前提是该位置合法。

用 `std::lower_bound` 快速得到答案（推荐）

std::lower_bound 返回第一个 ≥ target 的迭代器，所以它的前一个位置（如果存在）就是最后一个 target 的元素。这是最安全、最不易出错的方式。

实操建议：

先调用 std::lower_bound(arr.begin(), arr.end(), target)
检查返回迭代器是否等于 arr.begin()：若是，说明所有元素都 ≥ target，不存在小于 target 的元素
否则，prev(it) 对应的值就是目标；对应索引为 it - arr.begin() - 1

示例：

vector<int> arr = {1, 2, 4, 4, 5, 7};  
auto it = lower_bound(arr.begin(), arr.end(), 4); // 指向第一个 4（索引 2）  
if (it != arr.begin()) {  
    int idx = it - arr.begin() - 1; // 得到索引 1，arr[1] == 2，确实是最后一个 <h3>手写二分时容易踩的边界坑</h3>
<p>手写必须明确：搜索区间定义为 <code>[left, right]</code> 还是 <code>[left, right)</code>，且循环终止条件、更新方式必须严格匹配。常见错误是越界或漏判边界。</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>
<p>推荐使用左闭右开区间 <code>[l, r)</code>：</p>
<ul>
<li>初始 <code>l = 0</code>, <code>r = arr.size()</code>
</li>
<li>循环条件为 <code>l </code>
</li>
<li>每次 <code>mid = l + (r - l) / 2</code>，若 <code>arr[mid] ，说明 <code>mid</code> 可能是候选，但还要往右找更大下标 → <code>l = mid + 1</code></code>
</li>
<li>否则 <code>r = mid</code>
</li>
<li>退出后，<code>l - 1</code> 就是最后一个满足 <code>arr[i]  的索引（需检查 <code>l > 0</code>）</code>
</li>
</ul>
<p>注意：这里 <code>l</code> 最终停在第一个 ≥ <code>target</code> 的位置，和 <code>lower_bound</code> 行为一致 —— 所以手写逻辑其实就是在复现它。</p>
<h3>数组为空、全 ≥ target 或全 </h3>
<p>这三类边界情况必须显式判断，否则 <code>prev(it)</code> 或 <code>l - 1</code> 会越界。</p>
<ul>
<li>空数组：直接返回无效标识（如 -1）</li>
<li>所有元素 ≥ <code>target</code>：<code>lower_bound</code> 返回 <code>begin()</code>，此时无解</li>
<li>所有元素 target：<code>lower_bound</code> 返回 <code>end()</code>，此时答案是最后一个索引 <code>size() - 1</code>
</li>
</ul>
<p>手写版本中，<code>l == 0</code> 表示无解；<code>l == arr.size()</code> 表示全满足，答案为 <code>size() - 1</code>。</p>
<p>真正麻烦的不是算法逻辑，而是对 “不存在” 场景的统一建模——返回 -1？抛异常？还是用 <code>optional<int></int></code>？选哪种取决于你调用它的上下文，但别默认假设一定存在。</p></int>