JAVA / COLLECTIONS
Sorting and searching collections in practice
Sort a List with a composed Comparator and search it with Collections.binarySearch, including reading its negative result as an insertion point.
What you will learn
- Compose multi-key orders with Comparator.comparing(...).thenComparingInt(...)
- Sort in place with list.sort(order): it returns void and needs a mutable list
- Pass binarySearch the same comparator you sorted with, or the result is garbage
- Turn a negative binarySearch result into an insert index with -r - 1
Understanding Sorting and searching collections in practice
Sorting a List is an operation you apply, not a property the list keeps. list.sort(cmp) rearranges the elements in place and returns void, and the list has no memory that it was ever sorted, so a later add can break the order again. The ordering itself lives in the Comparator: Comparator.comparing(Employee::dept).thenComparingInt(Employee::salary) reads as "group by department, then by salary", and reversed() flips whatever order it is chained onto. Because List.sort is a stable merge sort, two elements the comparator calls equal keep their original relative order, which is why Bo still precedes Di in the output below.
Searching splits into two families with different preconditions. contains, indexOf and stream filters walk the list and decide with equals, so they work on any order and cost O(n) comparisons. Collections.binarySearch instead uses compareTo or a comparator and throws away half the range at each step, which is only sound if the list is already ordered by that same comparison, and Java does not verify it. Hand it a list sorted by a different key and you get a plausible-looking wrong number rather than an exception.
The return value packs two answers into one int. A non-negative value is the index of a matching element; a negative value is -(insertionPoint) - 1, so -r - 1 tells you where the key would belong. The extra offset exists because a missing key that belongs at the front has to be distinguishable from a match at index 0, and -0 is just 0. That negative number is therefore useful rather than an error signal: it is exactly the index to pass to list.add(index, element) to keep the list sorted.
import java.util.*;
public class SortSearchDemo {
record Employee(String name, String dept, int salary) {}
public static void main(String[] args) {
List<Employee> staff = new ArrayList<>(List.of(
new Employee("Ana", "sales", 52000),
new Employee("Bo", "eng", 74000),
new Employee("Cy", "sales", 61000),
new Employee("Di", "eng", 74000)));
Comparator<Employee> byDeptThenSalary =
Comparator.comparing(Employee::dept).thenComparingInt(Employee::salary);
staff.sort(byDeptThenSalary);
for (Employee e : staff) {
System.out.println(e.dept() + " " + e.salary() + " " + e.name());
}
int hit = Collections.binarySearch(staff,
new Employee("?", "sales", 61000), byDeptThenSalary);
System.out.println("hit: " + hit);
int miss = Collections.binarySearch(staff,
new Employee("?", "sales", 55000), byDeptThenSalary);
System.out.println("miss: " + miss + " -> insert at " + (-miss - 1));
}
}Binary search trusts, but never checks, that the list is already ordered by the exact comparison you search with.
Worked examples
Searching with the wrong ordering
Shows that binarySearch silently fails when the list was sorted by a different comparison than the search uses.
import java.util.*;
public class MismatchedSearch {
public static void main(String[] args) {
List<String> words = new ArrayList<>(
List.of("kiwi", "fig", "banana", "apple", "cherry"));
Comparator<String> byLength = Comparator.comparingInt(String::length);
words.sort(byLength);
System.out.println(words);
System.out.println(Collections.binarySearch(words, "kiwi"));
System.out.println(Collections.binarySearch(words, "kiwi", byLength));
}
}Example explained
Line 1words.sort(byLength) orders by 3, 4, 5, 6, 6 characters, so the list is not alphabetical at all.
Line 2The two-argument binarySearch assumes natural String order: it compares kiwi against apple, banana and cherry, keeps stepping right, and reports -6 although kiwi sits at index 1.
Line 3No exception is raised, because the sorted precondition is documented rather than checked, so this is a silent logic bug.
Line 4The three-argument call uses the same byLength comparator, so every comparison agrees with the stored order and the search lands on index 1.
Which lists can be sorted in place
Contrasts an immutable list, a fixed-size list view and a stream copy when you ask for sorted order.
import java.util.*;
public class SortInPlaceLimits {
public static void main(String[] args) {
List<Integer> immutable = List.of(3, 1, 2);
try {
immutable.sort(Comparator.naturalOrder());
} catch (UnsupportedOperationException e) {
System.out.println("List.of cannot be sorted in place");
}
List<Integer> fixed = Arrays.asList(3, 1, 2);
fixed.sort(Comparator.naturalOrder());
System.out.println(fixed);
List<Integer> source = new ArrayList<>(List.of(3, 1, 2));
List<Integer> sorted = source.stream().sorted().toList();
System.out.println(source + " " + sorted);
}
}Example explained
Line 1List.of returns an immutable list, and sort is a mutating operation, so it throws UnsupportedOperationException before any comparison happens.
Line 2Arrays.asList is fixed-size but allows set, so sort succeeds by rewriting the backing array in place.
Line 3stream().sorted().toList() produces a new sorted list and leaves source untouched, which is what you want when the input must stay in arrival order.
Keeping a list sorted with the insertion point
Uses the negative return value of binarySearch to insert new values without re-sorting.
import java.util.*;
public class KeepSorted {
public static void main(String[] args) {
List<Integer> scores = new ArrayList<>(List.of(10, 20, 30, 40));
for (int value : new int[] {25, 5, 45, 30}) {
int raw = Collections.binarySearch(scores, value);
int insertAt = raw >= 0 ? raw : -raw - 1;
scores.add(insertAt, value);
System.out.println(value + " raw=" + raw + " at=" + insertAt + " " + scores);
}
}
}Example explained
Line 1For 25 the search returns -3, and -(-3) - 1 = 2 is the index where 25 belongs between 20 and 30.
Line 2For 5 the raw result is -1, which means "absent, belongs at index 0", not the generic "not found" -1 used by indexOf.
Line 3For 30 the raw result is 4, a real match, so insertAt is used directly and the duplicate lands beside the existing 30.
Line 4Each add shifts the tail right and preserves the order, so the next binarySearch still meets its precondition.
Important notes
binarySearch returns some index whose element compares equal to the key, not necessarily the first such index and not necessarily an element that is equals to the key; step backwards from the hit if you need the earliest duplicate.
On a LinkedList, binarySearch still performs only about log2(n) comparisons but walks the links to reach each midpoint, so it is not the win it looks like; keep an ArrayList if you search a sorted list repeatedly.
Common mistakes
Sorting by a custom comparator and then calling the one-argument Collections.binarySearch, which assumes natural order: it returns a wrong index or a meaningless negative with no exception, so the failure surfaces later as missing or duplicated data.
Writing List<Employee> sorted = staff.sort(order); sort returns void so this does not compile, and the reflex fix of calling sort on List.of(...) compiles but throws UnsupportedOperationException at runtime.
Comparing by subtraction, as in (a, b) -> (int) (a.salary() - b.salary()): for large or long values the subtraction overflows and the sign flips, producing a silently wrong order or an IllegalArgumentException with the message "Comparison method violates its general contract!" from the sort.
Try it yourself
Change, predict, then run
Build an ArrayList of five city names, sort it with a comparator that orders by name length and then alphabetically, and print the result. Then binarySearch with that same comparator for a city that is not in the list, and print both the raw value and -r - 1.
Open the Java workspaceCheck your understanding
A list of strings was sorted with Comparator.comparingInt(String::length). You then call Collections.binarySearch(list, "kiwi") without passing that comparator, and "kiwi" is in the list. What is the likely result?
- A negative number, because the search assumes natural String order and discards the half that holds "kiwi"
- An IllegalArgumentException, because binarySearch detects that the list is not sorted in natural order
- The correct index, because binarySearch falls back to equals when the comparisons look inconsistent
- -1, the standard "not found" value returned by search methods in java.util
Show answer
binarySearch never scans the whole list; it trusts its precondition and halves the range, so with an ordering it was not sorted by it can walk right past "kiwi" and return an insertion point such as -6. Option 1 is tempting because sorting really can throw IllegalArgumentException with "Comparison method violates its general contract!", but that comes from the merge sort while sorting, not from binarySearch, which validates nothing. And -1 is not a generic miss marker here: it specifically means "absent, belongs at index 0".