C++实现二分查找时运行进入死循环且终端空白是什么原因?
问题根因
你的代码出现无限循环的核心原因是中间索引m的计算逻辑错误:原代码使用m = (l - f) / 2仅计算了左右边界差值的一半,未叠加左边界f的偏移量,导致m的取值完全不符合二分查找的区间要求,区间无法正常收缩,始终满足f<=l的循环条件,最终进入死循环。
错误场景复现
以你测试的查找数值7的场景为例:
- 初始状态f=0、l=9,m=(9-0)/2=4,对应数组值为5,7>5因此更新f=5
- 下一步计算m=(9-5)/2=2,此时m=2远小于左边界f=5,区间完全错乱,后续逻辑会反复修改f和l但永远无法跳出循环
修复方案
将所有m = (l - f) / 2的计算逻辑替换为m = f + (l - f) / 2,该写法同时避免了(f + l) / 2可能出现的整数溢出问题,兼容性更强。
修复后的完整biSearch函数如下:
int biSearch(int list[],int lenght,int t) { int f = 0; int l = lenght - 1; int m = f + (l - f) / 2; while(f<=l) { if (list[m] == t) { return m; } else { if (t < list[m]) { l = m - 1; m = f + (l - f) / 2; } else { f = m + 1; m = f + (l - f) / 2; } } } return -1; }
代码优化建议
你可以将m的计算逻辑放到while循环内部第一行,无需每次修改边界后重复书写计算代码,更简洁且不易出错:
int biSearch(int list[],int lenght,int t) { int f = 0; int l = lenght - 1; while(f<=l) { int m = f + (l - f) / 2; if (list[m] == t) return m; t < list[m] ? l = m - 1 : f = m + 1; } return -1; }
内容的提问来源于stack exchange,提问作者cachaçeiros do hawaii
相关产品推荐
相关产品推荐

