递归易栈溢出因每次调用压栈，大数据下深度超限；应控制深度、用尾递归、引用传参、前置边界检查；非递归用循环+双指针；模板化需泛型参数和可配置比较器。
递归写法：为什么容易栈溢出，又该怎么防
递归实现 binary_search 看似简洁，但实际在大规模数据或深度受限环境中风险明显。每次调用都压栈保存局部变量、返回地址和参数，当数组长度达到 10⁶ 级别时，递归深度可能逼近系统默认栈大小（如 Linux 默认 8MB，对应约 10⁵ 层调用），触发 Segmentation fault。
实操建议：
- 只在明确控制递归深度（如树高 ≤ 64）或教学演示场景下用递归；
- 若必须递归，改用尾递归形式（C++11 后部分编译器可优化），但需确保
return binary_search(...)是唯一返回语句，且无后续计算； - 传参务必用
const vector<int>&</int>或指针+长度，避免拷贝整个容器； - 边界检查要前置——比如
if (left > right) return -1;必须在函数开头，否则可能越界访问。
非递归写法：循环里三个关键点不能错
迭代版本靠 while (left 驱动，核心是维护搜索区间 <code>[left, right] 的闭合性。很多人写错，不是漏判相等，就是缩区间时逻辑反了。
实操建议：
- 初始化必须是
int left = 0, right = nums.size() - 1;，不是nums.size()，否则越界； - 缩区间时，
right = mid - 1和left = mid + 1不能写成= mid，否则可能死循环； -
mid计算推荐用left + (right - left) / 2，而非(left + right) / 2，防止整数溢出（尤其left、right接近INT_MAX时）； - 循环退出条件是
left > right，此时确定未找到，直接返回-1。
模板化与泛型支持：怎么让代码适配自定义类型
硬编码 int 类型会锁死复用能力。C++ 标准库的 std::lower_bound 能处理任意支持比较的类型，关键在抽象比较逻辑。
实操建议：
- 函数签名应为
template<typename t typename compare></typename>，把比较操作抽成参数，例如Compare comp； - 调用时可传
std::less()、lambda 或重载了operator 的类； - 注意迭代器版本比索引版本更通用——它不依赖随机访问，也能用于
std::list（虽然效率退化为 O(n)）； - 若用
auto mid = begin + (end - begin) / 2;，要求迭代器支持+和-，即必须是 RandomAccessIterator。
性能与调试陷阱：二分查找不是“写了就快”
算法复杂度是 O(log n)，但实际运行时间受缓存局部性、分支预测失败率影响很大。一个常见误区是认为“只要用了二分，就一定比线性快”，其实不然。
实操建议：
- 小数组（如 size
- 递归版因函数调用开销和栈帧管理，在同等数据量下通常比迭代慢 10%–20%；
- 调试时遇到“找不到明明存在的值”，优先检查：
nums是否已排序、是否升序但用了降序比较逻辑、mid是否被意外修改； - 使用
std::lower_bound前确认容器已排序，否则行为未定义——它不会帮你校验。
真正难的不是写出两种写法，而是根据数据规模、内存约束、类型特性，选对那个“刚好够用且不出错”的版本。很多线上 bug，就藏在把递归当默认、把 int 当万能类型的那一行代码里。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
