Personnalisation comparer dans bsearch()

Question

J'ai un tableau d'adresses qui pointent vers des entiers (ces entiers sont triés par ordre croissant). Ils ont des valeurs en double. Ex: 1, 2, 2, 3, 3, 3, 3, 4, 4 ......

J'essaie d'obtenir toutes les valeurs qui sont supérieures à certaine valeur (clé). À l'heure actuelle en train de mettre en œuvre à l'aide binaire recherche algo -

void *bsearch(
const void *key, 
const void *base, 
size_t num, 
size_t width, 
int (__cdecl *compare) (const void *, const void *) 
); 

Je ne suis pas en mesure d'y parvenir complètement, mais pour certains d'entre eux.

Y aurait-il un autre moyen d'obtenir toutes les valeurs du tableau , sans modifier l'algorithme que j'utilise?

Answer 1

Vous devriez regarder dans std::upper_bound

Par exemple, pour trouver l'adresse de la première valeur> 3:

const int data[] = { 1, 2, 2, 3, 3, 3, 3, 4, 4, ... }; 
size_t data_count = sizeof(data)/sizeof(*data); 

const int *ptr = std::upper_bound(data, data + data_count, 3); 

// ptr will now point to the address of the first 4 

Une fonction connexe est std::lower_bound.

Answer 2

Oui, vous pouvez utiliser une recherche binaire. L'astuce est ce que vous faites quand vous trouvez un élément avec la clé donnée ... sauf si vos indices inférieur et supérieur sont les mêmes, vous devez continuer la recherche binaire dans la partie gauche de votre intervalle ... c'est-à-dire, vous devriez vous déplacer la limite supérieure doit être le point milieu actuel. De cette façon, lorsque votre recherche binaire se termine, vous aurez trouvé le premier élément de ce type. Alors juste itérer sur le reste.

Answer 3

Comme Klatchko et GMan ont noté, la fonction STL vous donne exactement ce que vous demandez: std::upper_bound.

Si vous avez besoin de rester avec bsearch, cependant, la solution la plus simple peut être itérer vers l'avant jusqu'à ce que vous atteignez une nouvelle valeur.

void* p = bsearch(key, base, num, width, compare); 
while ((p != end) &&   // however you define the end of the array - 
           // base + num, perhaps? 
     (compare(key, p)==0)){ // while p points to an element matching the key 

    ++p; // advance p 
} 

Si vous voulez obtenir la première page qui correspond à la clé, plutôt que le premier qui est plus grande, il suffit d'utiliser --p au lieu de ++p. Que vous préfériez ceci ou une recherche binaire répétée, comme Michael suggère, dépend de la taille du tableau et du nombre de répétitions que vous attendez. Maintenant, le titre de votre question fait référence à la personnalisation de la fonction de comparaison, mais comme je comprends la question qui ne vous aidera pas ici, la fonction de comparaison doit comparer deux objets équivalents comme équivalents, donc ce n'est pas bon de reconnaître de plusieurs objets équivalents est le premier/dernier de son type dans un tableau. Sauf si vous avez eu un problème différent, en particulier concernant la fonction de comparaison?

Answer 4

Si vous avez un arbre de recherche binaire mis en œuvre, vous avez tree traversal algorithmes de le faire. Vous pouvez atteindre le nœud «limite supérieure» requis et simplement traverser l'ordre à partir de là. La traversée est plus simple que de parcourir plusieurs fois l'arbre, c'est-à-dire de parcourir au maximum n opérations, alors qu'une recherche n fois prendrait (n.log n) opérations.