-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 整除。

对于二分搜索，我通常会做的是，当范围足够小时，我将只对范围中的最后几个项目进行顺序搜索。

听起来您想要做的是搜索一个整数数组，该数组按升序排序并且其中可能包含重复项，并找到与您正在搜索的整数匹配的第一个数组元素。

一个问题是您是否希望这个正在搜索的函数提供匹配项的计数，或者只返回第一个并让函数的调用者检查任何其他项。

这是一个函数原型，供您考虑执行此操作的函数的接口。

// 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 回答