C++实现二分查找出现无限循环、部分查询结果异常问题

编写的C++二分查找程序存在两类异常：

• 仅能正确匹配数组内部分目标值，无法适配所有元素的查询场景
• 查询数组中不存在的目标值时，部分场景可正常返回-1标识未找到，部分场景会陷入无限循环无法退出

#include <iostream>
using namespace std;

int binary_search(int var, int arr[], int quant){
    
    int low, high, mid;
    int ind=0;
    bool found;
    
    low=0;
    high =quant-1;
    found = false;
    
    while ((found == false) && (low<=high)){
    
        mid = (high+low)/2+1;
 
        if (arr[mid] == var){
            ind=mid;
            found = true;
            cout<<ind<<endl;

        }
        else if (arr[mid]>var){
            high = mid-1;

            }
        else
            low = mid+1;
    
    }
    if (found == true)
        return ind;
    else
        return -1;
    

}

int main() {
    int a =4;
    int lst[7] = {0, 1, 2, 18, 19, 20, 25};
    int b = 7;
    cout<<binary_search(a,lst,b)<<endl;
}

核心逻辑错误为中点mid的计算多了无意义的+1偏移：

• 标准二分查找的中点计算应为mid = (low + high) / 2，更安全的防整数溢出写法是mid = low + (high - low)/2，代码中额外+1会导致中点计算偏移，当查找区间收敛到单元素/双元素边界时，会出现mid值固定、区间边界无法正常收缩的问题，直接触发无限循环，甚至出现数组越界访问。
• 触发死循环的典型场景（即示例代码中查找4的场景）：当low=3、high=3（区间只剩索引3的元素）时，按原代码逻辑计算mid=(3+3)/2+1=4，此时mid已经超出当前区间的上界high=3，arr[4]=19大于待查找值4，会执行high=mid-1=3，下一轮循环low和high仍然是3，mid又被计算为4，循环永远无法终止。
• 偏移的中点计算也会导致部分元素永远无法被mid命中，出现明明元素在数组中却查找失败的问题。

1. 删除mid计算时多余的+1操作，替换为安全的中点计算逻辑
2. 简化冗余状态变量，找到目标时直接返回下标即可，减少状态维护带来的出错可能

修复后的完整代码：

#include <iostream>
using namespace std;

int binary_search(int var, int arr[], int quant){
    int low = 0;
    int high = quant - 1;
    while (low <= high) {
        // 防溢出的中点计算，无多余偏移
        int mid = low + (high - low) / 2;
        if (arr[mid] == var) {
            cout << mid << endl;
            return mid;
        } else if (arr[mid] > var) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    // 循环正常结束说明没找到，直接返回-1
    return -1;
}

int main() {
    int lst[7] = {0, 1, 2, 18, 19, 20, 25};
    int len = 7;
    // 测试存在的元素
    cout << binary_search(18, lst, len) << endl;
    // 测试不存在的元素4，会正常返回-1不会死循环
    cout << binary_search(4, lst, len) << endl;
    return 0;
}

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