检查一个元素是否在数组中或者不是无限循环

Question

我试图在登录时间内查看一个数字是否在数组中，但此函数执行

else if(arr[(r-l)/2] < n) 

一直这样，就变成了无限循环。这是为什么？

int exists(int n, int *arr, int l, int r){
    if(l == r){

        if(arr[l] == n){
            return 1;
        }
        else{
            return 0;
        }
    }
    else if(arr[(r-l)/2] == n){
        return 1;
    }
    else if(arr[(r-l)/2] > n){
        return exists(n, arr, l, (r-l)/2);
    }
    else if(arr[(r-l)/2] < n){
        return exists(n, arr, (r-l)/2, r);
    }
}

int main(){
    node *root = NULL;

    int arr[5] = {1,2,3,4,5};
    printf("%d", exists(5, arr, 0, 4));

}

Answer 1

好吧，如果

else if (arr[(r-l)/2] == n) {

正在执行，那么是因为

if (l == r) {

错误

看起来您正在尝试进行二分搜索，如果是这样，则您的索引计算都是错误的。

int exists(int n, int *arr, int l, int r) {
    if (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] == n) {
            return 1;
        } else if (arr[mid] > n) {
            return exists(n, arr, l, mid - 1);
        } else {
            return exists(n, arr, mid + 1, r);
        }
    }

    return 0;
}