C++递归实现二分查找返回路径缺失却返回正确值的原因

问题复现代码 #

#include <iostream>
using namespace std;
int i = 0;
int binarySearch(int arr[],int left, int right, int item)
{
    int midpoint;
    bool found{false};
    if(left < right && !found)
    {
        midpoint = left + (right - left)/2;
        if(arr[midpoint]<item)
        {
            binarySearch(arr,midpoint+1,right,item);
        }
        else if(arr[midpoint]>item)
        {
            binarySearch(arr,left,midpoint-1,item);
        }
        else
        {
            found = true;
            return midpoint;
        }
    }

}
int main()
{
    int arr[] = {10,20,30,40};
    int x = binarySearch(arr,0,3,40);
    cout << x ;
}

现象原因 #

这是典型的未定义行为巧合式表现正常的情况，没有任何必然性，换编译选项、换编译器、调整测试用例大概率立刻出错，具体触发逻辑如下：

• 按照C++标准，非void函数走完控制流程却没有执行return语句，属于未定义行为，标准不保证任何输出结果，你现在看到的正确返回值是特定环境下的巧合。
• 目前主流x86平台的C++调用约定（cdecl、stdcall等），都会把int这类整数返回值存到eax寄存器中传递。当递归走到最深处命中目标元素、执行return midpoint时，正确的索引值会被写入eax。
• 上层的递归调用在调用完子递归函数后，没有执行任何会改写eax值的操作，也没有写自己的return语句就直接退出函数，eax里存的正确索引值没有被覆盖，就这么一路保留到了最上层的main函数调用处，看起来就像函数正确返回了结果。
• 这段代码本身还有其他明显逻辑缺陷：
  • found是每个递归栈帧独立的局部变量，每次进入函数都会被初始化为false，判断条件里的!found完全是无效代码，根本起不到找到元素就终止递归的作用。
  • 递归进入条件写的是left < right，当left == right也就是区间只剩单个元素时，根本不会进入查找逻辑，你现在测40能返回正确值只是刚好递归路径上命中了midpoint等于目标的分支，换成查找10、或者查找不存在的元素，马上就会返回垃圾值。

这类代码绝对不能用于生产环境，未定义行为表现出来的“正常”是最不可靠的，只要环境稍有变动，程序就可能输出乱值甚至直接崩溃。

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