c - 尝试二分查找

Question

我正在尝试从数组结构中二进制搜索字符串。我不断收到段错误或无限循环。我想知道我做错了什么。

int binsearch(struct person d[25], int low_int, int high_int, char search[15])
{
    int mid_int;
    printf(".");

    mid_int = ((high_int - low_int)/2);
    mid_int = mid_int + low_int;

    if(strcmp(search, d[mid_int].name) == 0)
        return mid_int;

    if(low_int > high_int)
        return -1;
    else if(strcmp(search, d[mid_int].name) > 0)
    {
        binsearch(d, mid_int+1, high_int, search);
    }
    else
    {
        binsearch(d, low_int, mid_int-1, search);
    }
}

每当我添加“mid_int = mid_int + low_int”时，它都会给我一个直接的段错误。当我把它拿走时，它会无限循环打印“.....”，然后导致段错误(句点显示搜索需要多少循环)。

Answer 1

首先，如果您想从中获得任何结果，您必须在递归 binsearch() 调用中使用 return 关键字。

然后在访问结构数组之前进行 if if(low_int > high_int) 检查，这样您就不会越界访问元素。

假设您使用有效参数调用该函数，代码应该可以工作。

binsearch( d , 0 , d_size-1 , "Search" ) ;

注意函数定义:

int binsearch(struct person d[25], int low_int, int high_int, char search[15])

相当于

int binsearch(struct person d[], int low_int, int high_int, char search[])

在这种情况下，尺寸 25 和 15 没有任何作用。您将必须传递数组的大小。这已经由 low_int 处理，d 的 high_int 和 search 应该以 nul 终止，因为它是一个字符串。