C++二分查找程序运行时控制台无限输出2的问题求助

核心死循环原因 #

• 二分查找边界更新逻辑错误：当前的边界更新规则会导致min和max相邻时无法退出循环：比如当min=1、max=2时，按照你的mid计算规则mid = 1 + (min+max)/2，得到的mid固定是2。如果此时nums[mid]大于目标值，你将max赋值为mid，那min和max永远保持1和2的差值，永远不满足min == max的退出条件，就会无限打印2。
• 数组排序顺序和查找逻辑不匹配：你构造data数组时，每次将新元素插入到数组头部，最终得到的是降序排列的数组，但你写的binSearch逻辑完全是按照升序数组设计的：升序数组中nums[mid] > 目标值说明目标在左半区，而在降序数组中这个判断对应的是目标在右半区，逻辑完全错位，这也是触发边界死循环的直接诱因。

其他存在的bug #

• randrange函数实现错误：你每次调用randrange都执行srand(time(0))初始化随机种子，time(0)精度为秒，短时间内多次调用会拿到完全相同的随机数。正确的做法是把srand(time(0))放到main函数初始化位置，整个程序生命周期只调用一次。
• 二分查找mid计算的溢出风险：你当前的(min + max)/2在min和max都很大时会出现整数溢出，正确的写法是min + (max - min)/2。
• 随机数取模逻辑错误：原代码rand() % y + x生成的随机数范围不符合[x,y]的预期，需要先计算区间长度再取模。

修复后的代码示例 #

升序数组版本（适配常规二分查找逻辑） #

#include "libraries.cpp"

// 修正后的随机数生成函数
int randrange(int x,int y){
    int random = rand() % (y - x + 1) + x;
    return random;
}

// 修正后的二分查找
int binSearch(vector<int> nums, int number){
    int min = 0;
    int max = nums.size() - 1;
    while(min <= max){
        int mid = min + (max - min)/2;
        if(nums[mid] > number){
            max = mid - 1;
        }else if(nums[mid] < number){
            min = mid + 1;
        }else{
            return mid;
        }
        cout << mid << endl;
    }
    return -1;
}
    
int main(){
    srand(time(0));
    vector<int> data;
    // 改用push_back直接生成升序数组
    for(int i = 0; i <= 1000; i++){
         data.push_back(i);
    }
    
    auto start = high_resolution_clock::now();  
    cout << binSearch(data,randrange(1,1000)) << endl;
    auto stop = high_resolution_clock::now(); 
    cout << duration_cast<microseconds>(stop - start).count() << endl; 
    return 0;
}

内容的提问来源于stack exchange，提问作者Aztro