1

我对以下两个陈述有点困惑。

下面的程序是finds the index of an element out of a sorted array[no duplicates] using binary search.

int bin(int *arr,int l,int h,int k)
{
    int mid;
    if(l>h)
            return -1;
    if(l==h)
    {
            return arr[l]==k?l:-1;
    }
    else
    {
            mid=(l+h)>>1;
            if(arr[mid]==k)
                    return mid;
            else if(k>arr[mid])
                    bin(arr,mid+1,h,k);
            else
                    bin(arr,l,mid-1,k);
    }
}

我在程序中没有任何问题[工作完美]：

我对以下两个陈述感到困惑：

bin(arr,l,mid-1,k); http://ideone.com/p1o5U
返回 bin(arr,l,mid-1,k); http://ideone.com/lMhgB

使用上述任何语句都会给出正确的结果。
哪个语句在时间方面更有效？
How the program is working fine even without return statement?

4

3 回答 3

0

该程序在使用不同的编译器编译时会产生不同的结果：

#include <stdio.h>

int bin(int *arr,int l,int h,int k)
{
    int mid;
    if(l>h)
            return -1;
    if(l==h)
    {
            return arr[l]==k?l:-1;
    }
    else
    {
            mid=(l+h)>>1;
            if(arr[mid]==k)
                    return mid;
            else if(k>arr[mid])
                    bin(arr,mid+1,h,k);
            else
                    bin(arr,l,mid-1,k);
    }
}

int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int main(void)
{
  int i;
  for (i = 0; i <= 11; i++)
    printf("bin(%d): %d\n", i, bin(arr, 0, 9, i));
  return 0;
}

输出（编译器：打开 Watcom C/C++ 1.9）：

>nrv.exe
bin(0): 0
bin(1): 1
bin(2): 2
bin(3): 3
bin(4): 4
bin(5): 4
bin(6): 6
bin(7): 7
bin(8): 8
bin(9): 9
bin(10): 10
bin(11): 11

输出（编译器：MinGW gcc 4.6.2）：

$ nrv.exe
bin(0): -1
bin(1): 0
bin(2): 1
bin(3): 2
bin(4): 3
bin(5): 4
bin(6): 5
bin(7): 6
bin(8): 7
bin(9): 8
bin(10): 9
bin(11): -1

我不敢说我​​在程序中没有任何问题[工作完美]。您的bin()函数调用未定义的行为。

于 2012-06-23T11:15:23.003 回答
0

即使没有返回语句，程序如何正常工作？

在这种情况下，我想说在实践中没有区别，因为递归结束于 return 语句，与你给它的参数无关（是的，即使你没有在最后两个调用中指定它）。然而，这是一个编译器特定的细节，你不应该依赖它！

哪个语句在时间方面更有效？

您可能会认为带有 return 语句的那些更有效，因为在这种情况下它不需要阅读“else”检查，但是差异非常小。

但是请注意，如果没有 return 语句，它被认为是“不正确的”，即使它“有效”，并且 -Wall 应该给你警告。

另见这个类似的问题。从那个答案复制：

您看到的可能是由于某些架构上的函数通过将众所周知的寄存器设置为该值（i386 上的 eax）返回的实现细节（整数值）引起的。因此，如果最底层的递归调用确实返回并设置了这个寄存器，并且中间的调用没有踩到那个寄存器，你会看到它有点工作。但是，您不能依赖它。

编辑：更改了措辞，以不暗示该行为是故意优化。不知道是不是。无论如何，有些编译器会做而有些则不会。

于 2012-06-23T10:41:34.217 回答
0

题外话：如果你无论如何都要使用递归，你可以通过消除下边界来大大简化程序，并用指针代替。

#include <stdio.h>

int bin(int *arr, int n, int k);
int bin(int *arr, int n, int k)
{
    int mid;
    if (n <= 0) return -1;

    mid = n / 2;
    if (arr[mid] == k) return mid;
    if (k < arr[mid]) return bin(arr, mid, k);

    n = bin(arr+mid+1, n-(mid+1), k);
    return (n<0) ? n : mid+1+n;
}

int main(void)
{
    int array[] = {0,1,2,3,4,5,6,7,8,9,10,11};
    int result, val;

    for (val= -2; val < 15; val++) {
        result = bin(array, 10, val);
        printf("Val=%d -> %d\n", val, result);
        }
return 0;
}
于 2012-06-23T13:05:23.437 回答