为什么我编写的C++非递归二分查找函数无法正常工作？

你的代码存在两个关键逻辑错误，导致无法正确工作：

1. 循环内未更新中间位置midpoint #

你仅在函数开头计算了一次midpoint，但每次调整first或last缩小搜索区间后，必须重新计算新的中间位置。否则永远用初始的midpoint值判断，完全无法正确缩小搜索范围。
比如你的测试用例中，初始midpoint为3（对应值43），目标是12：第一次判断43>12，将last改为2，但midpoint仍为3，下一轮循环还是拿arr[3]（43）和12对比，反复修改last直到循环结束，最终返回0，根本找不到正确下标1。

2. 未找到目标时的返回值有歧义 #

当前未找到目标时返回0，但0是数组的合法下标（比如查找元素4时，下标0是正确结果），这会让调用者混淆「找到下标0」和「未找到目标」两种情况。应该返回-1这类无效下标值。

修正后的代码 #

#include <iostream>

int binary_search(int arr[], int size, int target)
{
    int first = 0;
    int last = size - 1; 
    
    while(first <= last)
    {
        // 每次循环重新计算当前区间的中间位置
        int midpoint = first + (last - first) / 2; 
        if(arr[midpoint] == target)
        {
            return midpoint;
        }
        else if(arr[midpoint] < target)
        {
            first = midpoint + 1;
        }
        else
        {
            last = midpoint - 1;
        }
    }
    // 未找到目标返回无效下标
    return -1; 
}

int main()
{
    int arr[] = {4, 12, 23, 43, 50, 60, 230, 290};
    int size = sizeof(arr)/sizeof(arr[0]);
    int target = 12;
    int result = binary_search(arr, size, target);
    
    if(result != -1)
    {
        std::cout << "找到目标，下标为：" << result;
    }
    else
    {
        std::cout << "未找到目标";
    }
    return 0;
}

额外优化提示 #

计算midpoint时用first + (last - first)/2替代(first + last)/2，可以避免first和last数值过大时的整数溢出问题。

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