バイナリ検索で一致する値をすべて見つける方法はありますか？

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をスキップしないでください。 1回の検索では<、もう一方では<=を使用します。 [細かいことがあり、キーが見つからないか、片側にある場合にはデバッグが必要な場合があります。]

繰り返し値が少ない可能性がある場合：単一の検索を実行して最初のオカレンスを探します。次に、直線的に走査して「他端」を見つける。