了解神秘工作的递归二进制搜索算法

Question

在赋值时,我必须使用递归二进制搜索算法输出索引而不是True/False而不修改参数.我度过了一段非常艰难的时期,但在诉诸半试错之后,我偶然发现了这个烂摊子:

#include <iostream>
#include <math.h>
#include <climits>

using namespace std;


int BinarySearch(int arr[], int len, int target) {

    int temp = 0;
    int mid = len/2;

    if (len <= 0) return INT_MIN;  // not found
    if (target == arr[mid]){
        return mid; // found
    }

    if (target < arr[mid]){
        temp = BinarySearch(arr, mid, target);
    }

    else {
        temp = mid+1 + BinarySearch(arr+mid+1, len-mid-1, target);              
    }
}

即使在通过可视化工具运行之后,我也完全不知道它为什么会起作用.它对更改的代码非常敏感,当它无法找到目标时我无法输出-1,所以我至少总是输出一个负数.

我真的不需要它固定,我只是想知道它是如何工作的,因为看起来甚至没有使用递归调用的输出.谢谢.

Answer 1

它是未定义的行为(参见例如,为什么在没有返回值的情况下流出非void函数的末尾不会产生编译器错误？).

编译器似乎偶然返回temp,可能是因为它是函数内声明的第一个局部变量.回归温度会解决它.