C++如何实现二分查找算法的递归与非递归版本-C++-PHP中文网

递归版二分查找必须严格控制边界以避免栈溢出或死循环，关键在于每次递归缩小搜索范围且终止条件覆盖所有退出路径，常见错误是未正确处理left>right而直接返回-1。

c++如何实现二分查找算法的递归与非递归版本

递归版二分查找必须控制好边界，否则栈溢出或死循环

递归实现的关键在于每次调用都必须缩小搜索范围，且终止条件要覆盖所有退出路径。常见错误是写成 left 却在递归调用时传入 <code>mid 而非 mid - 1 或 mid + 1，导致区间不收缩。

正确做法是：当 target != arr[mid] 时，左半段递归调用传 left, mid - 1，右半段传 mid + 1, right；终止条件为 left > right，返回 -1。

int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2; // 防止整型溢出
    if (arr[mid] == target) return mid;
    if (target <ul>
<li>务必用 <code>left + (right - left) / 2</code> 计算 <code>mid</code>，避免 <code>left + right</code> 溢出</li>
<li>递归深度最大为 <code>O(log n)</code>，对超大数组（如千万级）仍安全，但调试时注意编译器默认栈大小限制</li>
<li>函数参数建议全用 <code>const</code> 引用传递数组，避免拷贝开销</li>
</ul>
<h3>非递归版要注意 while 循环的更新顺序和退出条件一致性</h3>
<p>非递归版本更常用，但新手常把 <code>left</code> 和 <code>right</code> 更新写反，或在 <code>while</code> 条件里用 <code> 却在分支里漏掉某一边的更新，造成无限循环。</code></p>
<p>核心原则：只要区间非空（即 <code>left ），就继续查；每次比较后，要么排除 <code>mid</code> 本身，要么排除它左边/右边全部元素。</code></p>
<p></p>
<pre class="brush:php;toolbar:false;">int binarySearchIterative(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <ul>
<li>
<code>while</code> 条件必须与递归终止条件一致，即 <code>left ，不是 <code></code></code>
</li>
<li>更新 <code>right = mid - 1</code> 和 <code>left = mid + 1</code> 是刚性要求，不能写成 <code>right = mid</code> —— 否则可能卡在单元素区间反复循环</li>
<li>该版本无函数调用开销，缓存友好，适合高频调用场景（如在线服务中的索引查询）</li>
</ul>
<h3>当数组含重复元素时，标准二分只返回“某个”位置，需额外处理找左右边界</h3>
<p>原题中的递归/非递归版本都只解决「是否存在」和「任一位置」问题。如果需求是找第一个或最后一个出现位置（例如 <code>lower_bound</code> / <code>upper_bound</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>
<p>关键差异在于：相等时不立即返回，而是继续向左（找首次）或向右（找末次）收缩区间。</p>
<p>例如找左边界：</p>
<p></p>
<pre class="brush:php;toolbar:false;">int lowerBound(const vector<int arr int target left="0," right="arr.size();" while mid="left" if else return><ul>
<li>这里用 <code>left  作循环条件，<code>right</code> 初始化为 <code>arr.size()</code>（开区间习惯），避免 -1 判断</code>
</li>
<li>相等时设 <code>right = mid</code>，不是 <code>mid - 1</code>，才能保证不跳过首个匹配点</li>
<li>返回前应检查 <code>left</code> 是否在有效范围内且 <code>arr[left] == target</code>，否则说明不存在</li>
</ul>
<h3>C++ 标准库已有成熟实现，业务代码优先用 <code>std::lower_bound</code> 和 <code>std::binary_search</code>
</h3>
<p>手写二分容易出错，尤其在边界、符号、溢出、迭代器类型上。STL 版本经过充分测试，支持任意满足 <code>RandomAccessIterator</code> 的容器，且内联优化充分。</p>
<p>常用组合：</p>
<p></p>
<pre class="brush:php;toolbar:false;">// 判断存在性
bool found = binary_search(arr.begin(), arr.end(), target);
<p>// 查找首个不小于 target 的位置
auto it = lower_bound(arr.begin(), arr.end(), target);</p><p>// 查找首个大于 target 的位置
auto it2 = upper_bound(arr.begin(), arr.end(), target);</p><p>// 二者结合得重复区间 [it, it2)
int count = distance(it, it2);</p>