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 == nmiddle == 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;
        }
//...

またはあなたのifelseスタイルで：

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 に答える