J'ai une mission qui me demande de créer une fonction de recherche binaire qui recherchera une matrice de structures contenant des dates pour un mois spécifié, puis d'imprimer toutes ces entrées avec des mois correspondants.
J'ai un très difficile Temps d'obtention de la recherche binaire correctement lorsque je recherche de multiples valeurs et que je ne peux pas sembler comprendre où je vais vous tromper. p>
Voici ma fonction de recherche binaire: p> xxx pré>
et voici ma fonction principale: p>
const int MAX = 50;
int main()
{
Event* event_pointers[MAX];
int count, userMonth;
char userString[80];
count = readEvents(event_pointers, MAX);
sort_desc(event_pointers, count);
display(event_pointers, count);
cout << "\n\nEnter a search string: ";
cin.getline(userString, 80, '\n');
cin.ignore();
linsearch(event_pointers, count, userString);
sort_date(event_pointers, count);
display(event_pointers, count);
cout << "\n\nEnter a month to list Events for: ";
cin >> userMonth;
cin.ignore();
binsearch(event_pointers, count, userMonth);
for (int j = 0; j < count; j++) //Cleanup loop
delete event_pointers[j];
cout << "\nPress any key to continue...";
(void)_getch();
return 0;
}
3 Réponses :
Ne définissez pas ces indices avec bInsearch. Recherchez une occurrence que de la boucle vers le bas et vers le haut jusqu'à ce que les conditions échouent. Quelque chose comme
Pour concevoir une fonction de recherche binaire correcte, n'essayez pas de deviner la solution, il est difficile de le faire correctement. Utilisez la méthode des invariants de boucle. La fonction qui trouve la première occurrence est appelée introduisons la variable Ces gammes représentent des éléments examinés jusqu'à présent. Initialement, L'algorithme suivant implémente cette idée: ici nous Peut réutiliser des variables analysons maintenant votre mise en œuvre. Je peux déduire les invariants de boucle suivants: Ce sont les mêmes invariants, avec est cassée. Avec cette condition, la plage Vous pouvez analyser la deuxième boucle de la même manière. Dans cette boucle au moins une affectation de C'est potentiellement une boucle infinie. Si La première approche, avec deux gammes à moitié ouvertes est bénéfique Imo. Il est symétrique et est plus facile à raisonner. Si aucune valeur n'a été trouvée, inférieur_bound Dans la bibliothèque standard, utilisons également ce nom ici aussi: Dernière : Auto Dernier = premier + taille . Nous recherchons un point de transition pt , tel que dans la plage [premier, pt) , tous les éléments ont des valeurs [pt, dernier) , tous les éléments ont des valeurs > = valeur . Introduisons deux itérateurs (pointeurs) gauche et droit avec les invariants de boucle:
[premier, gauche) Tous les éléments ont des valeurs [droite, dernier) Tous les éléments ont des valeurs > = valeur .
gauche = premier et droit = Dernier , de sorte que les deux gammes sont vides. À chaque itération, l'un d'entre eux sera élargi. Enfin, gauche = droite , donc la plage totale [premier, dernier) a été examiné. Des définitions ci-dessus, il suit que pt = droite . d'abord et dernier pour représenter gauche et droit . Je ne l'ai pas fait pour clarifier.
[premier, faible) - Tous les éléments ont des valeurs (haut, dernier) - Tous les éléments ont des valeurs > = valeur .
droit remplacé par haut + 1 . Le tandis que la boucle est correct, mais la condition, qui peut être réécrit comme [premier, faible) contiendra tous les éléments avec des valeurs <= valeur . Cela correspond au Upper_bound . La comparaison doit être << / code>, pas <= . MID est incorrecte. haut = bas + 1 , puis MID = faible , et que vous définissez haut sur moyen + 1 = haut . Vous modifiez ni faible , ni élevé , et la boucle devient infinie. <<
dernier = premier + taille est renvoyé, ce qui est un choix naturel pour représenter la fin de la gamme. Vous devriez rechercher first_index et last_index après les boucles. Et si elles n'ont pas été réaffectées et maintiennent toujours -1 ?
1 Définissez votre exemple comme cet exemple, 2 éléments de tri comme, p> 3 utilise p> std::equal_range(elements.begin(), elements.end(), your_target_month);
Cela peut aider à utiliser un IDE pour passer à travers et voir ce qui se passe