Search for the smallest element in a list after some value

Question

Consider a list of integers <1,5,10> (assume sorted in ascending fashion).

Given an integer, say, key = 6, is there a utility method that returns the smallest element after key (in this case it would be 10)?

NB: Looping through the elements in the list and comparing it with key is an obvious way to do it, but I'm just wondering if there exist a utility method to do the same thing :)

Answer 1

Have you considered Binary Search? Collections has a binarySearch method which you could use.

From the Collections binarySearch documentation:

Returns:

index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

I will let you figure out how you can use the return value of Collections.binarySearch to get the answer you need.

Answer 2

Binary search works, but if in fact you have a sorted set of values, then instead of a List, a SortedSet (or even better a NavigableSet), is the most natural data structure of choice.

Here's an example usage:

    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]"

There's also NavigableMap counterpart that can be even more useful in some scenarios.