Rechercher le plus petit élément dans une liste après une certaine valeur

Question

Considérons une liste d'entiers <1,5,10> (assumé trié de façon ascendante).

Étant donné un nombre entier, par exemple, key = 6, existe-t-il une méthode d'utilité qui retourne le plus petit élément après key (dans ce cas, il serait 10)?

NB: Boucler à travers les éléments dans la liste et en le comparant avec key est une façon évidente de le faire, mais je me demande s'il existe une méthode utilitaire pour faire la même chose :)

Answer 1

recherche binaire fonctionne, mais si en fait, vous avez un ensemble de valeurs triées, puis au lieu d'un List, un SortedSet (ou encore mieux un NavigableSet), est la structure de données la plus naturelle de choix.

Voici un exemple d'utilisation:

NavigableSet<Integer> nums = new TreeSet<Integer>(
     Arrays.asList(9,1,5,7,3) 
    ); 

    System.out.println(nums); // "[1, 3, 5, 7, 9]" 

    System.out.println(nums.first()); // "1" 
    System.out.println(nums.last()); // "9" 

    System.out.println(nums.higher(3)); // "5" 
    System.out.println(nums.lower(8)); // "7" 

    System.out.println(nums.subSet(2,8)); // "[3, 5, 7]" 
    System.out.println(nums.subSet(1, true, 5, true)); // "[1, 3, 5]" 

Il y a aussi NavigableMap contrepartie qui peut être encore plus utile dans certains scénarios.

Answer 2

Avez vous avez considéré Binary Search? Collections a une méthode binarySearch que vous pourriez utiliser.

De la documentation binarySearch Collections:

Retours:

index de la clé de recherche, si est contenu dans la liste; sinon, (- (point d'insertion) - 1). Le point d'insertion est défini comme étant le point à laquelle la clé serait inséré dans la liste: l'indice de le premier élément supérieur à la clé , ou list.size(), si tous les éléments dans la liste sont inférieur à la clé spécifiée . Notez que ce garantit que la valeur de retour sera être> = 0 si et seulement si la clé est trouvé.

Je vais vous laisser comprendre comment vous pouvez utiliser la valeur de retour de Collections.binarySearch pour obtenir la réponse dont vous avez besoin.