Comment utiliser la recherche binaire sur 2 tables de données triées en c

Question

Je cherche comment utiliser la recherche binaire dans le langage c.

Je commencerai par,

i ont une struct

struct keyval{ 
unsigned short key[2]; 
unsigned short val[2]; 
}; 

que vous pouvez voir c'est un struct avec 2 tableaux de courts métrages qui peuvent contenir 2 valeurs courtes.

puis la mémoire allouer à ces structures. cela me permet de stocker beaucoup de ce type de structure en mémoire. Je passe par quelques boucles et remplit les codes 1 avec struct keyval's

struct keyval *codes1 = malloc(sizeof(struct keyval)*(0x1000000)); 
struct keyval *codes2 = malloc(sizeof(struct keyval)*(0x1000000)); 

puis dans une autre boucle, je remplis les codes2 avec struct keyval

ces données auront été remplies sur la base d'une clé d'itération. Donc, fondamentalement, il sera automatiquement trié par valeur de clé.

puis trier mes données sur la valeur val. en utilisant la fonction c qsort et ma propre fonction de comparaison si le short dans l'emplacement 0 du tableau val de l'un est inférieur au short dans la même position de l'autre struct puis retourne -1 et ainsi de suite.

qsort(codes1,SIZE_OF_CODES1, sizeof(struct keyval), compare); 
qsort(codes2,SIZE_OF_CODES2, sizeof(struct keyval), compare); 

int compare(const void *a, const void *b){ 
    struct keyval *ia = (struct keyval *)a; 
    struct keyval *ib = (struct keyval *)b; 

    if(ia->val[0] > ib->val[0]){ 
     return 1; 
    }else if (ia->val[0] < ib->val[0]){ 
     return -1; 
    }else{ 
     return (ia->val[1] - ib->val[1]); 
    } 

}

maintenant c'est là où je suis coincé

je dois être en mesure de recherche binaire pour chaque valeur codes1 contre les valeurs codes2. et quand codes1[i].val == codes2[i].val je peux imprimer les valeurs de codes1 [i] .key puis codes2. [I] .key

ma tentative est en tant que telle

while(e <= SIZE_OF_CODES1){ 

    struct keyval *found = (struct keyval*) bsearch(&codes1[e],codes2,SIZE_OF_CODES2,sizeof(struct keyval),compare); 

    if(found){ 
     printf("\n found key = %08x %04x value = %04x %04x", found -> key, found -> key[1],found->val[0],found ->val[1]); 
    } 

    e++; 
} 

le code ci-dessus ne trouvez pas si les données correspondent aussi, je suis certain qu'il ya des endroits dans le code où il correspond

// ajouté modifier

---

juste fait un de bug, et j'ai trouvé que lorsque bsearch appelle la fonction de comparaison, à chaque fois qu'elle est appelée, toutes les valeurs associées à ia sont nulles mais ib est correcte.

la méthode de tri est correcte

---

quelqu'un pourrait me diriger dans la bonne direction sur la façon de mettre en œuvre une recherche binaire, je reçois très coincé

mon ancienne fonction de comparaison

int compare(const void *a, const void *b){ 
struct keyval *ia = (struct keyval *)a; 
struct keyval *ib = (struct keyval *)b; 

if(ia->val[0] > ib->val[0]){ 

    return 1; 
}else if(ia->val[0] < ib->val[0]){ 
    return -1; 
}else{ 
    if(ia->val[1] > ib->val[1]){ 
     return 1; 
    }else if(ia->val[1] < ib->val[1]){ 
     return -1; 
    }else{ 
     return 0; 
     } 
} 

}

Answer 1

pour comparer les listes que vous décrivez, étape thr Ough codes1, puis faites un bsearch() sur codes2 pour chaque entrée dans codes1. Vous pouvez réutiliser comparer.Je ne suis pas sûr si SIZE_OF_CODES1 et 2 sont des variables ou des définitions, je suppose qu'ils reflètent le nombre d'éléments dans chaque tableau.

struct keyval *src=codes1; 
struct keyval *dest=code2; 
struct keyval *p 
int i=0; 
while(i< SIZE_OF_CODES1) 
{ 
    if((p=(struct keyval *)bsearch(src, dest, SIZE_OF_CODES2, sizeof(struct keyval), compare))!=NULL) 
     printf("duplicate codes1: %d %d codes2: %d %d\n", src->key,src->val, p->key, p->val); 
    i++ 
}