c - C中的二进制搜索递归算法问题

Question

好的，所以我得到了这个功能

int bin(int value, int size, int array[])

我应该在“array[]”中找到“value”，但这里的问题是，在大多数情况下，我们有一些类似的东西

int bin(int value, int max, int min, int array[])

从逻辑上讲，这部分的递归要容易得多，因为我仍然可以传递我所在的数字，并记住数组的大小。

int bin(int array[], int value, int min, int max)
{
    if(max < min)
        return -1;
    else
    {
        int mid = min + (max - min)/2;

        if(array[mid] > value)
            return bin(array, value, min, mid-1);
        else if(array[mid] < value)
            return bin(array, value, mid+1, max);
        else
            return mid;
    }

但是由于我只能传递 1 个整数，我该如何调整这个算法呢？从本质上讲，我只能做这样的事情，但我知道这在逻辑上是行不通的。不过，有没有办法让我看到数组的大小？我试过了，但数字不正确。

   int bin(int array[], int value, int size)
    {
            int mid = size/2;

            if(array[mid] > value)
                return bin(array, value, size-(size/2));
            else if(array[mid] < value)
                return bin(array, value, size+(size/2));
            else
                return mid;
    }

Answer 1

您还需要显式传递基数：

int
bin(int array[], int value, int size)
{
        int mid = size/2;

        if(array[mid] > value)
            return bin(array, value, size/2);
        else if(array[mid] < value)
            return bin(&array[mid], value, size/2);
        else
            return mid;
}

注意“if(array[mid] < value)”情况下的“&array[mid]”

每次，您都需要搜索正确的一半数组，使用 base + offset 副最小/最大索引

Answer 2

使用具有不同参数集的方法的目的是使该方法易于为用户调用。这在递归中很常见。

具有
int bin(int value, int size, int array[])签名的用户可以使用公共方法。

然后应该有带有
int bin(int value, int max, int min, int array[])签名的私有内部辅助方法。

关键是，调用这个方法的人会想要传入数组的大小，而不是开始和结束索引（因为对他们来说，开始索引应该总是 0，结束应该总是 size-1）而且它是使用带有这样预设参数的方法是不好的做法。

具有开始和结束值（最小值和最大值）的辅助方法用于递归调用以实现更有效的计算，并且它对用户隐藏了不必要的参数。

您的方法应如下所示：

int bin(int value, int size, int array[]) {
    return bin(value, size - 1, 0, array);
}

Answer 3

int * binSearch (int *arr,int size, int num2Search)

{

    if(size==1)

        return ((*arr==num2Search)?(arr):(NULL));

    if(*(arr+(size/2))<num2Search)

        return binSearch(arr+(size/2)+1,(size/2),num2Search);

    if(*(arr+(size/2))==num2Search)

        return (arr+(size/2));

    return binSearch(arr,(size/2),num2Search);

}

在我的函数中，您获得相同的参数并返回值的地址。