Est-Il possible d'appliquer binaire de recherche à la liste des liens pour trouver un élément?
J'ai lu une question ,est-il possible d'appliquer une recherche binaire sur un lien de la liste?
Depuis liste de liens n'autorise pas l'accès aléatoire, cela semble pratiquement impossible.
Nul n'a de toute façon de le faire?
Vous devez vous connecter pour publier un commentaire.
Le principal problème, outre le fait que vous n'avez pas de constante de temps d'accès à la liste des éléments, c'est que vous n'avez aucune information sur la longueur de la liste. Dans ce cas, vous n'avez aucun moyen de "couper" la liste en 2 moitiés.
Si vous avez au moins une borne de la liste liée longueur, le problème est résoluble en temps O(log n), avec un saut de la liste, en effet. Sinon rien ne vous sauver de la lecture de l'ensemble de la liste, donc O(n).
Donc, en supposant que la liste est triée, et vous savez sa longueur (ou au moins la longueur maximale), oui il est possible de mettre en œuvre une sorte de recherche binaire sur une liste liée. Ce n'est pas souvent le cas.
Avec une simple liste chaînée, vous ne pouvez pas faire de recherche binaire directement, depuis l'accès aléatoire sur les listes chaînées est O(n).
Si vous avez besoin d'une recherche rapide, arbre-comme des structures de données (R/B arbre, trie, tas, etc.) offrent beaucoup de les avantages d'une liste chaînée (relativement bon marché aléatoire d'insertion /délétion), tout en étant très efficace dans la recherche.
Pas avec un classique de la liste liée, pour les raisons que vous avez de l'état.
Mais il y a une structure qui ne permet pas à un formulaire de recherche binaire qui est dérivée à partir de listes chaînées: Skip lists.
(Ce n'est pas trivial à mettre en œuvre.)
J'ai une fois mis en place quelque chose comme ça pour une liste liée individuellement triés contenant les clés. J'ai besoin de trouver plusieurs touches en elle (en sachant que l'un d'entre eux au début, le reste a été en dépend) et je voulais éviter d'en parcourant la liste encore et encore. Et je ne savais pas la liste de longueur.
Donc, j'ai fini par faire ça... je créé 256 pointeurs de point à la liste des éléments et leur fit point pour les 256 premiers éléments de la liste. Dès que toutes les 256 ont été utilisés et un 257th était nécessaire, j'ai laissé tomber la impaires valeurs de pointeur (1,3,5,etc), compactés, la paire (0,2,4,etc) dans les 128 premiers pointeurs et la poursuite de l'affectation de la moitié restante (128) de pointeurs pour le reste, cette fois, ignorant tous les autres élément de la liste. Ce processus se répète jusqu'à la fin de la liste, à quel point ces pointeurs ont été pointant vers des éléments espacés de façon égale tout au long de l'ensemble de la liste. J'ai ensuite pu faire une simple recherche binaire à l'aide de ces 256 (ou moins) de pointeurs de raccourcir la liste linéaire de recherche à 1/256e (ou 1/quel que soit l'-th) de la liste originale de longueur.
Ce n'est pas très fantaisie ou puissant, mais peut aussi parfois être suffisant perf amélioration avec de légères modifications de code.
Vous pouvez faire une recherche binaire sur une liste liée. Comme vous le dites, vous n'avez pas accès aléatoire, mais vous pouvez toujours trouver l'élément à un index spécifique, à partir de le début de la liste ou dans une autre position. Ainsi, une simple recherche binaire est possible, mais lente par rapport à la recherche binaire d'un tableau.
Si vous aviez une liste où les comparaisons ont été beaucoup, beaucoup plus cher qu'une simple liste de la traversée, puis une recherche binaire serait moins cher qu'un linéaire de recherche pour convenablement de la taille des listes. La recherche linéaire nécessite
O(n)comparaisons etO(n)nœud traversals, alors que la recherche binaire nécessiteO(log n)comparaisons etO(n log n)nœud traversals. Je ne sais pas si c'O(n log n)lié est serré, les autres le sont.Selon moi, il n'y a pas de façon de faire une recherche dans la liste Liée dans la recherche binaire manière. En binaire de recherche, nous avons l'habitude de trouver out 'milieu' de la valeur de tableau, ce qui est impossible avec les listes, comme les listes sont la structure où nous devons utiliser rigoureusement le "démarrer" (Nœud de pointage de très 1er noeud de la liste) pour parcourir à l'un de nos éléments d'une liste.
Et dans la gamme, nous pouvons aller à l'élément spécifique à l'aide de l'INDEX, ici pas question de l'Index (en Raison de l'Accès Aléatoire indisponibilité dans les listes chaînées).
Donc, je pense que la recherche binaire n'est pas possible avec une liste liée dans les pratiques habituelles.
pour l'application de la recherche binaire sur la liste liée, vous pouvez conserver une variable de comptage qui doit parcourir la liste, et de retourner le nombre total de nœuds. Aussi, vous auriez besoin de garder une variable de type int dire INDEX dans votre classe de nœud qui doit incrémenter lors de la création de chaque nouveau nœud. après quoi, il sera facile pour vous de diviser la liste en 2 moitiés et de les appliquer de recherche binaire sur elle.