2

我编写了以下程序来实现排序数组的二进制搜索：

    int flag=0;

    void binarysearch(int x, int a[], int m, int n)
    {
        int middle=(m+n)/2;
        if(a[middle]==x)
        {
            printf("%d has been found at postion %d!\n", x, middle+1);
            flag=1;
        }
        else
        if(x > a[middle])
            binarysearch(x, a, middle, n);
        else
        if(x < a[middle])
            binarysearch(x, a, m, middle);
    }

    main()
    {
        int i, size, x;
        int a[100];
        printf("Enter the size of the list : ");
        scanf("%d", &size);
        printf("Enter the list items in ascending order : \n");
        for (i=0; i<size; i++)
        scanf("%d", &a[i]);
        printf("Enter the element to be found : ");
        scanf("%d", &x);
        binarysearch(x, a, 0, size-1);
        if(flag != 1)
        printf("%d has not been found in the list!", x);
    }

这个程序的问题是，binarysearch如果尝试搜索不在列表中的项目，该函数会一遍又一遍地递归调用自己。因此，flag变量变得完全没有意义。

程序是否有可能告诉用户他是否正在尝试执行这样的搜索（搜索不在数组中的东西）？

我假设这是不可能的，因为它是二进制搜索算法中的一个基本缺陷。请赐教。

4

4 回答 4

8

m == n在开始时检查。

if(m == n)
{
    if(a[n] == x) { printf("found\n"); }

    return;
}

如果没有x，你继续用middle == nand称呼自己middle == m。

于 2012-09-24T17:08:09.433 回答
2

您的函数应该使用返回值并返回在数组中找到它的索引

   int binarysearch(int x, int a[], int m, int n)
{
    int middle=(m+n)/2;
    if(a[middle]==x)
    {
        printf("%d has been found at postion %d!\n", x, middle+1);
        return middle;
    }
    else
    if(x > a[middle])
        return binarysearch(x, a, middle, n);
    else
    if(x < a[middle])
        return binarysearch(x, a, m, middle);

   //if it is not found in the whole array
   return -1;


}
于 2012-09-24T17:10:56.037 回答
1

您需要一个简单的案例来打破递归，即n == m. 如果这成立 和x != a[middle]，那么这个元素不在数组中：

void binarysearch(int x, int a[], int m, int n)
    {
        int middle=(m+n)/2;
        if(n == m && x != a[middle])
        {
            printf("%d is not in the array", x);
            return;
        }
//...

或者你的 if else 风格：

void binarysearch(int x, int a[], int m, int n)
    {
        int middle=(m+n)/2;
        if(n == m && x != a[middle])
        {
            printf("%d is not in the array", x);
        }
        else
        if(a[middle]==x)
//...
于 2012-09-24T17:09:39.797 回答
0

我认为您对递归缺乏一些基本的了解。递归函数在达到其基本情况时应返回值。如果您知道我的意思，您的代码最终会导致“StackOverflow”:)

于 2012-09-24T17:10:02.807 回答