C++中std::midpoint在二分查找中如何避免溢出并优化性能？

本文共计1128个文字，预计阅读时间需要5分钟。

由于整数溢出不是错误，而是直接触发未定义行为（UB），以下是一个简化的示例：

常见误判是“数据没那么大，不会出事”，但编译器不会帮你检查运行时值；更麻烦的是，这种 bug 往往只在特定硬件或优化等级下暴露，调试成本极高。

• (low + high) / 2 在有符号整型上风险最高，无符号类型虽不溢出但会回绕（right 时 <code>right - left 变成极大正数）
• 即使你用 size_t，也得额外写 if (high >= low) 判断，否则减法回绕后除以 2 还是错的
• 手写 low + (high - low) / 2 是可行替代，但需确保类型一致、括号完整，且无法覆盖指针场景

std::midpoint 在二分中怎么写才对

它不是“换个函数名就行”，关键在类型匹配和调用上下文。C++20 要求两个参数必须是同一类型，且对指针有严格限制。

正确写法示例：

立即学习“C++免费学习笔记（深入）”；

int binary_search(const std::vector<int>& v, int target) { int left = 0; int right = static_cast<int>(v.size()) - 1; // 确保 signed while (left <= right) { int mid = std::midpoint(left, right); // ✅ 同为 int，安全 if (v[mid] == target) return mid; if (v[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }

• 别传 size_t 和 int 混合：例如 std::midpoint(0, v.size() - 1) 编译失败——v.size() 是 size_t，0 是 int
• 指针场景下，只能用于原生指针：如 std::midpoint(arr, arr + n) 合法，但 std::midpoint(v.begin(), v.end()) 不合法（迭代器不是指针）
• 若用 std::vector::iterator，得先转成指针：std::midpoint(&v[0], &v[0] + v.size()) 或用 std::data(v)

浮点数和指针场景下，std::midpoint 表现差异很大

它对三类输入行为完全不同，不能一概而论。

• 整型：真正防溢出，等价于 a + (b - a) / 2，且对负数舍入方向明确（向零取整）
• 指针：唯一不可替代的用途——std::midpoint(p, q) 保证指针算术不溢出，哪怕 p 和 q 差值接近 PTRDIFF_MAX；手写 p + (q - p) / 2 中的 q - p 若超 ptrdiff_t 范围就是 UB
• 浮点数：std::midpoint(x, y) 实际就是 (x + y) / 2，标准没要求它规避精度损失；当 x = 1e30、y = 1.0 时，仍可能因加法丢失精度。此时应改用 std::fma(x, 0.5, y * 0.5) 或手动分支判断量级

C++17 及更早项目怎么安全过渡

别硬升 C++20，也别抄网上错的位运算实现（比如 (a & b) + ((a ^ b) >> 1) 对负数完全错误）。兼容方案要分类型处理，且保持 constexpr 友好。

一个轻量级替代模板：

template <class T> constexpr T safe_midpoint(T a, T b) { if constexpr (std::is_integral_v<T> && std::is_signed_v<T>) { using U = typename std::make_unsigned<T>::type; return static_cast<T>( static_cast<U>(a) + (static_cast<U>(b) - static_cast<U>(a)) / 2 ); } else if constexpr (std::is_pointer_v<T>) { auto diff = b - a; return a + diff / 2; } else { return (a + b) / 2; } }

• 对 int，safe_midpoint(INT_MIN, INT_MAX) 返回 -1（正确）
• 不依赖编译器扩展，C++11 起可用；但注意指针版本要求 operator- 和 operator+ 可用（原生指针天然支持）
• 如果项目已用 C++20 且确认 GCC 10+ / Clang 11+ / MSVC 19.28+，直接用 std::midpoint——它还额外处理了 nullptr 等边界

真正容易被忽略的是：它只管“算得对”，不管“用得对”。传进去的 low 和 high 是否构成有效区间、是否在容器范围内、是否满足 low <= high，std::midpoint 一概不校验。这些仍是业务逻辑责任。