-1 
#include<stdio.h>
#include<stdlib.h>
int input(int *a)
{
    int n,i;
    printf("enter the no of elements:");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("enter the element:");
        scanf("%d",a++);
    }
    return n;
}
int key_input(int *a,int key)
{
    int k;
    printf("enter the key value which have to be searched in the array of no's provided:");
    scanf("%d",&k);
    return k;
}
void binary_search(int *a,int n,int key)
{
    int low=0;
    int high=n-1;
    int mid;
    while(low<=high)
    {
        mid=(high+low)/2;
        if(key == a[mid])
        {
            printf("the key:%d is found at location:%d in the array",key,mid);
            if(key==a[mid+1])
            {
                binary_search(a+mid+1,n-mid-1,key);
            }
            if(key==a[mid-1])
            {
                binary_search(a,n-mid-1,key);
            }
            if(key != a[mid-1] || key != a[mid+1])
                break;
        }
        else if(key < a[mid])
            high=mid-1;
        else if(key>a[mid])
            low=mid+1;
    }
}
int main()
{
    int arr[100];
    int n=input(arr);
    int key=key_input(arr,n);
    binary_search(arr,n,key);
    return 0;
}

これは私が二分探索のために書いたコードです。キーが存在するすべての配列の場所を見つけたいです。たとえば、入力 4,4,4,4 に対してキーを 4 にするとします。出力には配列のすべての場所 (0 ～ 3) が含まれているはずですが、コードの何が問題なのかわかりません。コードは無限に実行されています。誰か助けてください。

4

1 に答える 1

0

おそらく何が起こっているのかというと、高低を移動するためのコードが、中値が常に同じになるポイントに到達し、無限ループが発生することです。これは、配列リスト内のアイテムの数と、アイテムの数が2で均等に割り切れるかどうかによって異なります。

バイナリ検索で通常行うことは、範囲が十分に小さい場合、範囲内の最後のいくつかの項目を順次検索することです。

昇順で並べ替えられ、アイテムが重複している可能性のある整数の配列を検索し、検索対象の整数に一致する最初の配列要素を見つけることをお勧めします。

1つの質問は、検索を実行しているこの関数で一致するアイテムの数をカウントするか、最初のアイテムを返し、関数の呼び出し元に他のアイテムをチェックさせるかです。

これを行う関数へのインターフェースを検討するための関数プロトタイプを次に示します。

// search the integer array iValueArray which is a sorted list of integers
// and return the index 0 to iNoArrayElements - 1 of the first integer matching
// the value specified in iSearchValue.  if a match is not found then return -1
int FindFirstMatch (int iSearchValue, int *iValueArray, int iNoArrayElements);

この関数は次のようになります。

int FindFirstMatch (int iSearchValue, int *iValueArray, int iNoArrayElements) {
int iRetIndex = -1;

if (iNoArrayElements > 0) {
    int iLowIndex = 0;
    int iHighIndex = iNoArrayElements - 1;
    int iMidIndex = (iHighIndex - iLowIndex) / 2 + iLowIndex;

    while (iLowIndex <= iHighIndex) {
        int iCompare = (iSearchValue - iValueArray[iMidIndex]);

        if (iHighIndex - iLowIndex < 5) {
            // range is small so just do a straight sequential search
            for (iMidIndex = iLowIndex; iMidIndex <= iHighIndex; iMidIndex++) {
                int iCompare = (iSearchValue - iValueArray[iMidIndex]);
                if (iCompare == 0) {
                    // search value equals the mid so we have found a match
                    // now we need to move lower until we find the first of
                    // the series of matching items.
                    iRetIndex = iMidIndex;
                    break;
                }
            }
            break;
        }
        if (iCompare < 0) {
            // search value is lower than mid so move to range below mid
            iHighIndex = iMidIndex;
        } else if (iCompare > 0) {
            // search value is higher than mid so move to range above mid
            iLowIndex = iMidIndex;
        } else {
            // search value equals the mid so we have found a match
            // now we need to move lower until we find the first of
            // the series of matching items.
            iRetIndex = iMidIndex;
            break;
        }
        iMidIndex = (iHighIndex - iLowIndex) / 2 + iLowIndex;
    }
}

if (iRetIndex > 0) {
    while (iRetIndex > 0 && iValueArray[iRetIndex - 1] == iSearchValue) {
        iRetIndex--;
    }
}
return iRetIndex;

}

于 2012-08-05T19:15:27.393 に答える