c - c中的二分查找-必须找出键的所有数组位置

Question

#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;
}

这是我为二分搜索编写的代码。我想找出 key 所在的所有数组位置。例如，如果我将输入 4,4,4,4 的 key 指定为 4。输出应该包含数组的所有位置(0-3)，但我不知道代码有什么问题，它无限运行。请有人帮助我。

Answer 1

很可能发生的情况是，用于移动高点和低点的代码达到了中间值始终相同的点，从而导致无限循环。这取决于数组列表中的项目数以及项目数是否能被 2 整除。

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

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

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

这里有一个函数原型(prototype)，供您考虑执行此操作的函数的接口(interface)。

// 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;

}