C++如何使用二分查找法搜索数组-C++-PHP中文网

优先使用std::lower_bound因其底层经过充分测试、边界和迭代器处理更健壮；手写易出错，如边界更新遗漏、mid计算溢出；需确保数组有序，返回首个≥target的迭代器，须与end()比较判断是否找到。

c++如何使用二分查找法搜索数组

std::lower_bound 为什么比手写二分更值得优先用

绝大多数情况下，直接调用 std::lower_bound 是最稳妥的选择——它底层是经过充分测试的二分实现，处理边界、迭代器类型、自定义比较逻辑都更健壮。手写容易在 left/right 边界更新时漏掉一个元素，或在 mid 计算时整数溢出（尤其在大数组中）。

使用前提：数组必须已升序排列（或按指定比较规则有序）。若无序，先排序或改用 std::find。

std::lower_bound 返回第一个 ≥ target 的迭代器；找不到则返回 end()
要判断是否找到，必须和 end() 比较，不能只看值是否等于 target（因为可能越界解引用）
支持自定义比较函数，比如降序数组要用 std::greater<int>()</int>

std::vector<int> arr = {1, 3, 5, 7, 9};
auto it = std::lower_bound(arr.begin(), arr.end(), 5);
if (it != arr.end() && *it == 5) {
    std::cout <h3>手写二分时最容易错的三个地方</h3>
<p>不是逻辑写不对，而是细节踩坑导致死循环或越界。常见错误现象：<code>while (left  卡住不动、<code>mid</code> 算出负数、查不到最后一个元素。</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>
<ul>
<li>区间定义必须统一：推荐闭区间 <code>[left, right]</code>，初始化 <code>right = size - 1</code>；更新时 <code>right = mid - 1</code> 和 <code>left = mid + 1</code> 对称，不易漏</li>
<li>
<code>mid</code> 必须写成 <code>left + (right - left) / 2</code>，避免 <code>(left + right)</code> 溢出（尤其 <code>int</code> 数组索引接近 <code>INT_MAX</code> 时）</li>
<li>循环退出条件选 <code>left ，否则闭区间会漏判 <code>left == right</code> 的情况</code>
</li>
</ul>
<pre class="brush:php;toolbar:false;">int binary_search(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <h3>搜索重复元素时，std::lower_bound 和 std::upper_bound 怎么配合用</h3>
<p>当数组含重复值（如 <code>{2,4,4,4,6}</code>），单靠 <code>std::lower_bound</code> 只能定位第一个 4；要找全部，需搭配 <code>std::upper_bound</code> 获取第一个 > target 的位置。</p>
<ul>
<li>
<code>std::lower_bound</code> → 第一个 ≥ target 的位置</li>
<li>
<code>std::upper_bound</code> → 第一个 > target 的位置</li>
<li>两者差值就是 target 出现次数；区间 <code>[lower, upper)</code> 内所有元素都等于 target</li>
<li>若 <code>lower == upper</code>，说明没找到</li>
</ul>
<pre class="brush:php;toolbar:false;">auto lo = std::lower_bound(arr.begin(), arr.end(), 4);
auto up = std::upper_bound(arr.begin(), arr.end(), 4);
int count = up - lo; // 3 in this case