二分查找以及差值二分查找

二分查找求中间下标两种写法的深度解析一、先搞懂mid (left right) / 2为什么会出问题1. 核心问题整数溢出Integer Overflow在 C 语言中int类型是有符号整数有固定的取值范围常见 32 位系统-2^31 ~ 2^31-1即-2147483648 ~ 2147483647。当left和right都很大时left right的结果会超过int类型的最大值发生整数溢出结果变成一个负数有符号整数溢出是未定义行为C 标准不保证结果最终mid变成一个错误的负数下标导致数组越界、程序崩溃2. 举个直观的例子假设 32 位int系统最大值是2147483647left 2000000000right 2000000000正确的中间值(2000000000 2000000000) / 2 2000000000实际计算2000000000 2000000000 4000000000超过int最大值溢出后变成负数4000000000对应的有符号int是-294967296最终mid -294967296 / 2 -147483648完全错误二、mid left (right - left) / 2为什么安全1. 数学等价性先证明结果完全一致我们可以用代数推导证明两种写法数学上完全等价left (right - left) / 2 (2*left right - left) / 2 (left right) / 2✅ 结论两种写法的计算结果完全相同只是计算过程不同2. 为什么不会溢出right - left两个大整数相减结果一定是非负数且远小于int最大值因为right left差值最多是数组长度不会溢出(right - left) / 2差值除以 2结果更小绝对不会溢出left 差值/2left本身在int范围内加上一个小的差值也不会溢出3. 用刚才的例子验证left 2000000000right 2000000000right - left 0→0 / 2 0mid 2000000000 0 2000000000完全正确再举一个普通例子left 1right 10写法 1(110)/2 5.5 → 5整数除法向下取整写法 21 (10-1)/2 1 4.5 → 1 4 5结果完全一致三、两种写法的详细对比表对比维度mid (left right) / 2mid left (right - left) / 2数学结果与写法 2 完全等价与写法 1 完全等价溢出风险高leftright易超出int范围无全程不会溢出可读性直观一眼看懂是求平均值稍差需要理解变形逻辑适用场景小范围数组如长度 1e6无溢出风险所有场景尤其是大数据量、大下标C 语言标准溢出属于未定义行为可能导致程序崩溃完全符合标准安全可靠四、补充其他等价写法拓展知识除了上面两种还有两种常见的等价写法原理相同1. 位运算写法效率更高适合整数mid left ((right - left) 1); 1等价于/ 2整数右移 1 位相当于除以 2 向下取整效率比除法更高编译器优化更好是工业界常用写法注意只适用于无符号整数或非负数有符号负数右移是算术右移结果不同2. 另一种变形写法mid (left right) ((left ^ right) 1);原理a b (a b) 1 (a ^ b)再除以 2 得到平均值同样避免溢出但可读性差仅在特殊场景使用五、实际开发中的最佳实践1. 永远优先使用left (right - left) / 2这是工业界标准写法所有大厂、开源项目如 Linux 内核、Redis都用这个写法完全避免溢出且结果和原写法一致没有任何副作用即使是小范围数组也建议用这个写法养成良好习惯2. 特殊场景的注意事项无符号整数(left right) / 2溢出后会变成大的无符号数结果错误同样需要用安全写法浮点数求平均值不会有溢出问题浮点数范围大直接用(left right) / 2.0即可C/Java 等其他语言原理完全相同同样推荐用安全写法六、总结一句话记住(left right) / 2直观但有溢出风险仅适合小数据left (right - left) / 2安全无溢出结果完全一致是通用最佳实践核心本质通过改变计算顺序避免两个大数直接相加导致的溢出