Je me suis souvenu que le segment de mémoire peut être utilisé pour rechercher si un élément est dedans ou non avec une complexité de temps O (logN). Mais soudain, je ne peux pas obtenir les détails. Je peux seulement trouver getmin supprimer ajouter et ainsi de suite.Rechercher un élément dans un segment
Quelqu'un peut-il donner un indice?
Vous devez rechercher dans chaque élément du tas pour déterminer si un élément est à l'intérieur.
Une optimisation est cependant possible (nous supposons ici un tas maximum). Si vous avez atteint un nœud dont la valeur est inférieure à celle de l'élément que vous recherchez, vous n'avez pas besoin de chercher plus loin à partir de ce nœud. Cependant, même avec cette optimisation, la recherche est toujours O (N) (besoin de vérifier N/2 nœuds en moyenne).
Je pense que ce que vous cherchez est un BST (arbre de recherche binaire).
Inutile si vous avez déjà une file d'attente prioritaire et que vous voulez vérifier si elle contient un élément donné. – finnw
Est-ce entièrement vrai? Prenez le tas suivant comme exemple: '[5, 4, 1, 3]' Si je recherche ce tas (sous la forme d'un tableau) pour le numéro 3, je vais frapper 1 et, selon votre algorithme, arrêter ici conclure qu'il n'est pas dans le tas quand il est en fait? Est-ce que j'ai râté quelque chose? –
Avec l'optimisation, le sous-arbre avec la racine 1 ne sera pas recherché plus loin, car il ne peut pas contenir 3. 3 est dans un autre sous-arbre. Je suis d'accord qu'une recherche linéaire (par opposition à une recherche récursive) peut donner une mauvaise réponse. –
@JamesSanders C'est vrai dans tous les cas, même pour une recherche linéaire. L'arbre binaire complet aura la valeur 3 comme un enfant à gauche de 4, et 1 sera à la même hauteur que 4. Même si vous faites une recherche linéaire, l'optimisation dit que 4> 3, vous devez donc, au minimum , comparez les enfants de 4, en plus de tous les autres éléments à la même hauteur que 4. – lee