Comment puis-je trouver toutes les valeurs correspondantes avec une recherche binaire?

Question

Voici mon code pour trouver la position d'une valeur dans un tableau trié en utilisant une recherche binaire. Mon problème est que la valeur peut être présente dans mon tableau plus d'une fois, mais ma recherche montre seulement la position de la première correspondance trouvée. Je veux afficher la position de toutes les valeurs correspondantes. Comment puis-je trouver la position de toutes les valeurs dans mon tableau en utilisant la recherche binaire?

#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

S'il y a probablement beaucoup de valeurs répétées: Est-ce deux recherches binaires, pour trouver les positions de début et la fin de la série de valeurs « clés ». Ne pas terminer la recherche sur la correspondance exacte, et ne pas sauter mid; utilisez < pour la condition dans une recherche et <= pour l'autre. [Les détails seront difficiles et nécessiteront un débogage pour les cas où la clé est introuvable ou à une extrémité.]

S'il y a probablement peu de valeurs répétées: Effectuez une seule recherche pour trouver la première occurrence . Ensuite, scannez linéairement pour trouver "l'autre extrémité".