Recherche linéaire ou Recherche binaire ou binaire Recherche Arbre

Question

J'ai un petit doute ici ...

Si je sais qu'un élément de recherche dans une liste, par exemple contenant 32 éléments triés par ordre, est apparaissant dans les quatre premières positions ,

qui est le meilleur algorithme de recherche.

recherche linéaire au moins besoin de 4 itération .... recherche binaire au moins 5 itération Que diriez-vous arbre de recherche binaire .. il ne donne une meilleure solution dans ce cas ou est égal à la recherche binaire ...

Je crois que la recherche linéaire sera meilleure pour de telles circonstances.

quelqu'un peut-il confirmer cela s'il vous plaît?

Answer 1

Si vous savez que l'emplacement est dans les 4 premières positions, une recherche linéaire est préférable car vous ne devrez pas tester plus de 4 éléments. Avec une recherche binaire 32 = 5, vous devrez tester au maximum 5 éléments. En outre, pour une petite quantité d'éléments comme celui-ci, la différence de temps est négligeable et vous serez mieux servis en le gardant simple et en effectuant une recherche linéaire.

Vous pouvez également utiliser HashTable ou HashSet pendant O (1) temps, mais encore une fois, pour une petite quantité de données, une recherche linéaire serait probablement plus rapide que l'exécution d'une fonction de hachage.

Et si la petite différence a vraiment de l'importance, je suggère de le mesurer dans l'environnement où il va fonctionner.

Answer 2

vous pouvez faire une recherche binaire sur les 4 premiers éléments. ce sera lg 4 = 2 itérations! :-)

Answer 3

Avec exactement ce nombre d'éléments et l'application exacte que vous avez sous la main, un arbre de recherche binaire serait une surdétermination. De plus, pour résoudre le problème tel qu'il se présente actuellement, la recherche linéaire serait préférable car le nombre attendu d'itérations pour localiser un élément particulier l'emportera sur la recherche binaire.

Pour le scénario de la vie réelle, le problème présenté tel qu'il est sera très rare. Par conséquent, il est toujours préférable d'utiliser la recherche binaire sur les tableaux triés.

Answer 4

Si les données sont distribuées uniformément d'une manière ou d'une autre, il est judicieux d'utiliser la recherche par interpolation. En utilisant la connaissance de la distribution, vous avez une bonne chance de deviner la bonne position en une seule étape. La complexité attendue est O (log (log (n))).

Voici un lien vers mes pages, où je l'algorithme implémenté en Java: Algoritmy.net - interpolation search implementation