c - 如何通过二分查找获得所有匹配的值？

Question

这是我使用二分搜索查找排序数组中值的位置的代码。我的问题是该值可能多次出现在我的数组中，但我的搜索仅显示它找到的第一个匹配项的位置。我想输出所有匹配值的位置。我该如何解决我的问题？ 提前致谢。

#include<stdio.h>
#include<stdlib.h>

void aSort(int *a, int aLen){

int i, j;
for(i=0; i<aLen-1; i++){
    for(j=i+1; j<aLen; j++){
        if(a[i] > a[j]){
            int temp;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}
return;
}

void bSearch(int *a, int aSize, int key,int *rArr, int *ItemNum){

int start = 0;
int aEnd = aSize-1;
int mid = (start + aEnd) / 2;
*ItemNum = -1;

while(start<=aEnd){
    if(key == a[mid]){
        *ItemNum += 1;
        rArr[*ItemNum] = mid;
        break;
    }else if(a[mid] < key){
        start = mid + 1;
    }else{
        aEnd = mid - 1;
    }

    mid = (start + aEnd) / 2;
}

return;
}


int main(){
int n;
char i_type;
printf("Enter number of array element: \n");
scanf("%d", &n);

int a[n];
printf("Insert array element manual or automatic?\nIf manual press 'M' or press 'A' for automatic\n");
scanf("%*c%c", &i_type);

if(i_type == 'a' || i_type == 'A'){
    printf("The array elements is:\n");
    int i;
    for(i=0; i<n; i++){
        a[i] = rand()%100;
        printf("%d ", a[i]);
    }

}else{
    printf("Enter %d integer value: ", n);
    int i;
    for(i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    printf("The array elements is:\n");
    for(i=0; i<n; i++){
        printf("%d ", a[i]);
    }
}

aSort(a, n);
printf("\nNow the array is in ascending order:\n");
int i;
for(i=0; i<n; i++){
    printf("%d ", a[i]);
}
printf("\nEnter the key value which you want to find: ");
int key, numArr, rArr[n];
scanf("%d", &key);

bSearch(a, n, key, rArr, &numArr);
if(numArr == -1){
    printf("Item not found!\n");
}else{
    int i;
    for(i=0; i<=numArr; i++)
        printf("Your item found in %d position.\n", rArr[i]+1);
}


return 0;
}

Answer 1

如果可能有许多重复值:执行两次二分搜索，以查找“键”值运行的开始和结束位置。不要在完全匹配时终止搜索，也不要跳过 mid ;使用<对于一次搜索中的条件和 <=对于另一个。 [细节会很棘手，并且在找不到 key 或 key 位于一端的情况下可能需要进行一些调试。]

如果可能有几个重复值:执行一次搜索以查找第一个出现的值。然后，线性扫描找到“另一端”。