Meilleure façon de trouver une valeur dans List lorsque la liste est triée

Question

Disons que j'ai une Java ArrayList, qui est triée. Maintenant, je voudrais trouver l'indice de la valeur x. Quel serait le moyen le plus rapide (sans plus de 30 lignes de code) de le faire? Utilisation de la méthode IndexOf()? Itérer à travers toutes les valeurs dans une boucle simple? Utilisation d'un algorithme sympa? Nous parlons d'environ disons 50 clés entières.

Answer 1

Binary search, mais comme il n'y a que 50 articles, on s'en soucie (sauf si vous devez le faire des millions de fois)? Une recherche linéaire simple est plus simple et la différence de performance pour 50 articles est négligeable.

Modifier: Vous pouvez également utiliser la méthode intégrée java.util.Collections binarySearch. Sachez qu'il retournera un point d'insertion même si l'élément n'est pas trouvé. Vous devrez peut-être faire un couple supplémentaire de vérifications pour vous assurer que l'article est vraiment celui que vous voulez. Merci à @Matthew pour le pointeur.

Answer 2

tvanfosson a raison, le temps pour l'un ou l'autre sera très faible, donc à moins que ce code ne fonctionne très fréquemment, cela ne fera pas beaucoup de différence.

Cependant, Java a une fonctionnalité intégrée pour les recherches binaires de listes (y compris ArrayLists), Collections.binarySearch.

Answer 3

Si les clés ont une distribution acceptable, Interpolation Search peut être très rapide si l'on considère le temps d'exécution. Considérer l'heure de codage IndexOf() est le chemin à parcourir (ou une recherche binaire intégrée si disponible pour votre type de données (je viens de C# et je ne connais pas Java)).

Answer 4

import java.util.ArrayList; 
import java.util.Collections; 

ArrayList myList = new ArrayList(); 
// ...fill with values 

Collections.sort(myList); 
int index = Collections.binarySearch(myList, "searchVal"); 

Edit: code non testé