用C语言实现二进制搜索排序数组

Question

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

    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变量变得完全没有意义.

是否有可能程序能够告诉用户他是否正在尝试执行此类搜索(不在阵列中的某些内容)？

我假设它不可能,因为它是二进制搜索算法的基本缺陷.请赐教.

Answer 1

检查m == n开始.

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

    return;
}

如果没有x,你继续调用自己与middle == n和middle == m.