我在我的 C 二进制搜索代码中做错了什么？

Question

我正在研究二分搜索算法以准备我的编码面试，但是我的算法仅适用于最佳情况，即当搜索的数据位于中点时，O(1)。当我将值更改为更糟糕的情况（例如第一个位置）时，光标会卡住。

我知道二分查找有一个 O(log n) 更坏的情况，所以它应该不会花很长时间。我做错了吗？

#include <stdio.h>

int binary_search(int arr[], int left, int right, int data){
    // condition that runs only if true
    while(left <= right){
        int mid = (left + right) / 2;
        if(data == arr[mid]){
            return mid;
        }

        if(data > arr[mid]){
            binary_search(arr, mid+1, right, data);
        }

        binary_search(arr, left, mid-1, data);
    }
    return -1;
}

void main(){
    int arr[] = {1,2,3,4,5,6,7,8,9};
    int result = binary_search(arr, 0, (sizeof(arr)/sizeof(arr[0]) - 1), 2);
    (result == -1) ? printf("There was no record found\n") : printf("Your record was found at position %d\n", result+1);
}

Answer 1

您没有从函数中正确 return 触发无限递归。在递归调用 binary_search(arr, mid+1, right, data); 的地方，您需要将 return 值传播回调用函数。

此外，与您的问题无关，但在 C void main() 中在技术上是不合法的，即使您可能不会收到任何明确的错误。 main() 应该 return 始终是一个 int。

#include <stdio.h>

int binary_search(int arr[], int left, int right, int data){
    // condition that runs only if true
    while(left <= right){
        int mid = (left + right) / 2;
        if(data == arr[mid]){
            return mid;
        }

        if(data > arr[mid]){
            return binary_search(arr, mid+1, right, data);
        }

        return binary_search(arr, left, mid-1, data);
    }
    return -1;
}

int main(void){
    int arr[] = {1,2,3,4,5,6,7,8,9};
    int result = binary_search(arr, 0, (sizeof(arr)/sizeof(arr[0]) - 1), 2);
    (result == -1) ? printf("There was no record found\n") : printf("Your record was found at position %d\n", result+1);

    return 0;
}

Answer 2

您的代码无法正常工作，因为如果在第一次迭代中 data 不等于 arr[mid]，您的递归函数 return 就什么都不是。所以在这种情况下你将有一个无限递归。

但无论如何对于专业程序员来说，代码是非常非常薄弱的。

例如，您的函数可能不会为常量数组调用。（是否还需要一个不同名称的函数？）

该函数应该只有三个参数

return_type binary_search( const int a[], size_t n, int data );

如果函数 return 是目标元素的索引，那么它的 return 类型应该是 size_t 因为通常 int 类型无法容纳表达式 sizeof( a ) / sizeof( *a ).

的值

如果函数只检查给定值是否存在于数组中，那么它应该 return 0 或 1 并且它的 return 类型应该是 int 或 _Bool.

如果函数应该 return 目标值的位置，那么它应该 return 具有目标值的元素的第一个位置，与标准算法相同 std::lower_bound在 C++ 中。

复制标准 C 函数 bsearch 的相同缺点不是一个好主意，通常不会 return 具有目标值的第一个元素的位置。

您不得使用运算符 == 来比较值（尽管 C 中的比较函数使用此运算符），因为例如对于浮点数，您可能会得到错误的结果。您应该只使用运算符 <.

好吧，我们假设您的函数适用于元素类型为 int 且运算符 < 的数组。但是如果用户想使用自己的数组元素比较函数怎么办？

第二个问题，如果用户要使用元素类型为long long的数组或结构数组，他是否需要花时间再写一个二进制搜索函数？

我的建议：不要在面试中做任何作业。忽略那些试图操纵你和你的时间的公司。面试是平等伙伴的对话。如果您自己是一名合格的程序员，在简单的对话中很容易理解 "who is who"。 :)

我在我的 C 二进制搜索代码中做错了什么？

What am I doing wrong in my C binary search code?

c

arrays

algorithm

binary-search

function-definition