C++如何实现二分查找的变体：寻找最后一个小于等于目标的值-C++-PHP中文网

二分查找变体的核心逻辑是：基于有序数组，通过调整边界更新条件，使搜索区间持续收敛，最终锁定最左（第一个≥target）或最右（最后一个≤target）的合法位置；左边界需在nums[mid]==target时继续向左搜（r=mid−1），右边界则等价于upper_bound−1，二者均推荐闭区间[l,r]并独立执行两次二分。

c++如何实现二分查找的变体：寻找最后一个小于等于目标的值

二分查找变体的核心逻辑是什么

标准二分查找找的是「等于目标的第一个位置」，而「最后一个小于等于目标的值」本质是找右边界：它不关心是否相等，只保证 nums[i] ，且 <code>i 尽可能大。关键在于：当 nums[mid] 时，<code>mid 是合法候选，答案在 [mid, right] 区间，所以要保留 mid 并向右收缩 —— 即 left = mid（不是 mid + 1），否则会漏掉它。

为什么必须用左闭右闭区间且更新方式特殊

用 [left, right] 区间最直观，但传统写法中 left = mid + 1 和 right = mid - 1 不适用这个变体。因为我们要“保留”满足条件的 mid，所以：

当 nums[mid] ：<code>left = mid（不能 +1，否则跳过当前合法位置）
当 nums[mid] > target：right = mid - 1（必须缩右，因为 mid 已不合法）
循环条件必须是 left 或等价形式（如 <code>left + 1 ），否则会死循环 —— 因为 <code>left = mid 可能不推进

更稳妥的做法是用 while (left + 手动控制 <code>mid 向上取整：mid = left + (right - left + 1) / 2，避免 left 卡住。

完整可运行代码与边界处理要点

int lower_bound_last_le(vector<int>& nums, int target) {
    if (nums.empty()) return -1;
    int left = 0, right = nums.size() - 1;
    while (left <p>注意三点：</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>
<ul>
<li>
<code>mid</code> 必须向上取整，否则 <code>left</code> 在两数区间时永远不变（比如 <code>left=3, right=4</code>，向下取整得 <code>mid=3</code>，<code>left=mid</code> → 死循环）</li>
<li>退出时 <code>left == right</code>，需显式判断 <code>nums[left] ，因为数组可能全大于 <code>target</code></code>
</li>
<li>若目标比所有元素都小，返回 <code>-1</code>；若比所有元素都大，返回最后一个索引</li>
</ul>
<h3>和 STL 的 <code>upper_bound</code>、<code>lower_bound</code> 有什么区别</h3>
<p><code>std::lower_bound</code> 返回第一个 ≥ target 的位置，<code>std::upper_bound</code> 返回第一个 > target 的位置。你要的「最后一个小于等于 target 的位置」其实是 <code>upper_bound - 1</code>，前提是该位置存在且合法：</p>
<ul>
<li>先调用 <code>auto it = upper_bound(nums.begin(), nums.end(), target)</code>
</li>
<li>若 <code>it == nums.begin()</code>，说明没有 ≤ target 的元素，返回 <code>-1</code>
</li>
<li>否则返回 <code>it - nums.begin() - 1</code>
</li>
</ul>
<p>手写版本更可控，尤其在需要定制比较逻辑或处理非随机访问迭代器时；STL 版简洁但隐藏了边界检查细节，容易在 <code>it == begin()</code> 时越界解引用。</p>
<p>真正麻烦的是重复元素多时的语义理解 —— 「最后一个小于等于」不等于「最后一个等于」，前者包含所有更小的数，后者只看相等。别混淆这两者。</p></int>

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