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

二分查找找第一个小于 target 的位置等价于找最后一个 ≤ target−1 的位置，可用 std::upper_bound 返回位置前一个实现，不可误用 lower_bound 或写错边界条件。

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

二分查找找第一个小于 target 的位置，本质是 upper_bound 的反向变体

直接结论：C++ 标准库没有现成函数，但可以用 std::upper_bound 稍作调整，或手写二分逻辑。关键不是“找小于”，而是“找最后一个 ≤ target−1 的位置”——这等价于 std::upper_bound 返回位置的前一个（前提是存在）。

常见错误是误用 std::lower_bound 或把边界条件写成 left 却忘记处理空数组、全大于/全小于 target 的情况。

如果所有元素都 ≥ target，结果应为 -1（或按需返回 0 表示无合法位置）
如果所有元素都 nums.size() - 1
std::upper_bound(nums.begin(), nums.end(), target - 1) 在 target 为整数时可行，但对浮点数或自定义类型不通用

手写二分：左闭右闭区间，返回最右满足 nums[i]

推荐用 left 模式，更直观控制“最后一个小于”的行为。核心思路是：当 <code>nums[mid] 时，<code>mid 是候选答案，往右缩区间找更大的合法下标；否则往左缩。

int lower_than_target(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int ans = -1; // 初始化为无效值
    while (left <p>注意：<code>ans</code> 必须初始化为 -1，不能依赖循环外默认值；<code>mid</code> 计算用 <code>left + (right - left) / 2</code> 防溢出；该实现天然兼容空数组（<code>nums.size() == 0</code> → <code>right == -1</code> → 循环不进）。</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
														src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
													<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
												</div>
												<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>
<h3>用 std::upper_bound 替代手写：更安全但需理解偏移</h3>
<p><code>std::upper_bound</code> 找的是“第一个 > target 的位置”，所以 <code>std::upper_bound(nums.begin(), nums.end(), target - 1)</code> 等价于“第一个 ≥ target 的位置”，其前一个位置才是“最后一个 </p>
<ul>
<li>若 <code>it == nums.begin()</code>，说明没有元素 </li>
<li>否则返回 <code>std::distance(nums.begin(), it) - 1</code>
</li>
<li>对非整数类型（如 <code>double</code>），不能用 <code>target - 1</code>，得改用 <code>std::prev(it)</code> 并验证有效性</li>
</ul>
<p>更通用写法：</p>
<pre class="brush:php;toolbar:false;">
int lower_than_target_stl(const vector<int>& nums, int target) {
    auto it = std::upper_bound(nums.begin(), nums.end(), target - 1);
    if (it == nums.begin()) return -1;
    return std::distance(nums.begin(), --it);
}
</int>