The Project | About Us | Contribute | Donations | License

HOME

You reach the end of the module with all the pieces on the table. You know how to store elements in lists, guarantee uniqueness with sets, index by key with maps and model processing policies with queues and stacks. What is missing is the operation that cuts across all of them and that appears in practically every program: putting things in order and finding them.

Sorting and searching are not minor topics. Sorting is probably the most studied algorithmic operation in the history of computing, and the choice between linear search, binary search and access by key is one of the decisions with the greatest impact on the performance of a real system. In this lesson you will see the complete Comparable contract —including the mistake of subtracting integers that silently overflows—, the whole Comparator arsenal picked up from 04-06, the four sorting strategies with the criteria for choosing between them, what it means for a sort to be stable and why that is what allows sorting by successive criteria, and which algorithms Java really uses underneath.

Then, searching: linear, binary and by key, with the complexity table that decides between them and the exact interpretation of the negative value binarySearch returns. And at the end, the module's balance sheet: BiblioTech with an indexed, sortable catalogue, reports, a reservation queue and an undo stack... and the honest list of what is still fragile, which is exactly the syllabus of module 6.

Natural order with Comparable
The compareTo contract
The mistake of subtracting integers
Consistency with equals and what breaks without it
Comparator: external and multiple ordering
The catalogue of Comparator methods
The four sorting strategies
Stability and sorting by successive criteria
Which algorithm Java really uses
Searching: linear, binary and by key
binarySearch and its negative value
Collections utilities
Performance: sort once, search many times
Closing the module: the state of BiblioTech
Common Mistakes and Tips
Exercises

Natural order with `Comparable`

A class declares its natural order by implementing the Comparable interface:

public interface Comparable<T> {
    int compareTo(T other);
}

A single method, returning an int whose sign —not its value— is what matters:

Result	Meaning
Negative	`this` goes before `other`
Zero	They are equivalent as far as ordering goes
Positive	`this` goes after `other`

You already used Comparable in 04-07 when making Card sort by title. Here is the complete, correct implementation:

package com.nexussoftware.bibliotech.domain;

/** A bibliographic card with a natural order by title. */
public record Card(String title, String author, int year) implements Comparable<Card> {

    public Card {
        if (title  == null || title.isBlank())  { title  = "Untitled"; }
        if (author == null || author.isBlank()) { author = "Unknown"; }
        if (year < 1450 || year > 2100)         { year   = 0; }
    }

    /** Natural order: alphabetically by title. */
    @Override
    public int compareTo(Card other) {
        return this.title.compareTo(other.title);    // String already implements Comparable
    }
}

And this is how it is used, without telling anybody how to sort:

List<Card> cards = new ArrayList<>(List.of(
    new Card("Refactoring",     "Martin Fowler", 1999),
    new Card("Effective Java",  "Joshua Bloch",  2018),
    new Card("Design Patterns", "Erich Gamma",   1994)));

cards.sort(null);                        // null = natural order
Collections.sort(cards);                 // equivalent
System.out.println(cards.get(0).title()); // Design Patterns

TreeSet<Card> sorted = new TreeSet<>(cards);           // the TreeSet uses compareTo
Card smallest = Collections.min(cards);                // it does too

Many JDK classes already implement it: String (lexicographic order), all the numeric wrappers, Character, Boolean, the enums (by their ordinal, that is, by declaration order) and the java.time classes (10-05).

A well-implemented Comparable opens the doors to the whole Framework: sort with no arguments, TreeSet, TreeMap, PriorityQueue, Collections.max, Collections.min and binarySearch.

That said, Comparable has an important limitation: you can only define one natural order per class. If you need to sort materials by title, by rate and by type, you need Comparator. And there is a question worth asking before implementing Comparable: is there really one order that is the natural one for this type? For a String or a number, yes. For a Material, debatable. For a Loan, probably not. If in doubt, do not implement Comparable: use comparators.

The `compareTo` contract

compareTo has a contract as strict as equals's from 03-09, and breaking it produces unpredictable behaviour in sorted collections.

1. Antisymmetry. sgn(a.compareTo(b)) == -sgn(b.compareTo(a)) for all a and b. If A goes before B, B goes after A. And if a.compareTo(b) throws an exception, b.compareTo(a) must throw one too.

2. Transitivity. If a.compareTo(b) > 0 and b.compareTo(c) > 0, then a.compareTo(c) > 0. If A goes after B, and B after C, A goes after C. Without this property, the sort can loop or throw IllegalArgumentException: Comparison method violates its general contract!, an error that comes out of TimSort when it detects the inconsistency.

3. Consistency of ordering equality. If a.compareTo(b) == 0, then sgn(a.compareTo(c)) == sgn(b.compareTo(c)) for every c. "Tied" elements must behave identically towards third parties.

4. Consistency with equals (recommended, not compulsory). a.compareTo(b) == 0 should imply a.equals(b). It is the only one the compiler does not require, and the one that causes the most problems when it is ignored. It has a section of its own.

5. null does not take part. a.compareTo(null) must throw NullPointerException, not return a value. null has no position in an ordering.

Examples of violations that compile perfectly:

// VIOLATES antisymmetry: it always says "I go first"
@Override public int compareTo(Card other) { return -1; }

// VIOLATES transitivity: the order depends on something that changes
@Override public int compareTo(Card other) {
    return Double.compare(Math.random(), 0.5);
}

// VIOLATES consistency: it compares different fields depending on the case
@Override public int compareTo(Card other) {
    if (this.year > 2000) { return this.title.compareTo(other.title); }
    return Integer.compare(this.year, other.year);
}

The third one is the most dangerous because it looks reasonable. When sorting a list with TimSort, the algorithm assumes transitivity in order to skip comparisons; if the criterion changes depending on the element, the result can be an incorrect order or outright an exception in the middle of the sort.

The mistake of subtracting integers

This is the classic compareTo mistake, and it appears in an enormous amount of production code:

// WRONG: it looks correct and works... until it does not
@Override
public int compareTo(Card other) {
    return this.year - other.year;
}

The reasoning is tempting: if this.year is greater, the subtraction is positive; if it is smaller, negative; if they are equal, zero. And it works with years between 1450 and 2100.

The problem is overflow. An int runs from −2,147,483,648 to 2,147,483,647. If the subtraction goes outside that range, the result wraps around and changes sign:

int a = 2_000_000_000;
int b = -2_000_000_000;

System.out.println(a - b);                 // -294967296   <- NEGATIVE, and a > b !
System.out.println(Integer.compare(a, b)); // 1            <- correct

a is clearly greater than b, but the subtraction overflows and returns a negative, so compareTo claims the opposite. The result is a silently incorrect sort, a TreeSet that loses elements and a binarySearch that does not find what is there.

The solution is never to subtract. Use the static comparison methods, which are written precisely for this:

Integer.compare(a, b)      // for int
Long.compare(a, b)         // for long
Double.compare(a, b)       // for double: it also handles NaN and -0.0 properly
Boolean.compare(a, b)      // false < true
Character.compare(a, b)

// RIGHT
@Override
public int compareTo(Card other) {
    return Integer.compare(this.year, other.year);
}

The Double case deserves a separate mention. Subtracting doubles has an additional problem beyond overflow: the subtraction of two very close doubles can give 0.0 without them being equal, and besides, Double.compare correctly handles NaN and the distinction between 0.0 and -0.0, which a subtraction does not.

// WRONG
return (int) (this.rate - other.rate);       // 0.25 - 0.10 = 0.15 -> (int) 0 -> "equal"!

// RIGHT
return Double.compare(this.rate, other.rate);

That example is especially insidious: the cast to int truncates any difference smaller than 1, so all BiblioTech's rates would be considered equal.

A rule with no exceptions: never subtract to compare. Always use Type.compare(a, b).

Consistency with `equals` and what breaks without it

You already saw it in passing in 05-06 with TreeSet; here is the complete problem.

An ordering is said to be consistent with equals when a.compareTo(b) == 0 if and only if a.equals(b). That is: two elements tie in the ordering exactly when they are equal.

When that consistency is broken, sorted collections behave unexpectedly, because TreeSet and TreeMap use compareTo, not equals, to decide uniqueness.

package com.nexussoftware.bibliotech.domain;

/** A card with a natural order by YEAR: inconsistent with equals. */
record CardByYear(String title, String author, int year)
        implements Comparable<CardByYear> {

    @Override
    public int compareTo(CardByYear other) {
        return Integer.compare(this.year, other.year);   // only the year
    }
}

CardByYear a = new CardByYear("Effective Java",  "Joshua Bloch", 2018);
CardByYear b = new CardByYear("Design Patterns", "Erich Gamma",  2018);

System.out.println(a.equals(b));        // false: they are DIFFERENT cards
System.out.println(a.compareTo(b));     // 0:     but they TIE in the ordering

// In a List nothing happens
List<CardByYear> list = new ArrayList<>(List.of(a, b));
System.out.println(list.size());        // 2   correct

// In a TreeSet, it does
TreeSet<CardByYear> set = new TreeSet<>(List.of(a, b));
System.out.println(set.size());         // 1   <-- A CARD WAS LOST

// And contains lies
System.out.println(set.contains(b));    // true, even though b is not inside

An element has been lost silently. The TreeSet asked compareTo, got 0 and concluded that b was already there.

The same with TreeMap:

TreeMap<CardByYear, String> map = new TreeMap<>();
map.put(a, "Shelf A-3");
map.put(b, "Shelf B-1");
System.out.println(map.size());       // 1: b REPLACED a
System.out.println(map.get(a));       // Shelf B-1  <-- the wrong value

Compare with what happens in hash-based structures:

Collection	Decides uniqueness with	Inconsistent card-by-year
`List`	Nothing: it allows duplicates	2 elements, correct
`HashSet` / `HashMap`	`equals` + `hashCode`	2 elements, correct
`TreeSet` / `TreeMap`	`compareTo` / `compare`	1 element: one is lost
`PriorityQueue`	Nothing: it allows duplicates	2 elements, but arbitrary order between them

The solution is always the same: add tie-breaking criteria until the ordering is total, that is, until only genuinely equal elements tie.

@Override
public int compareTo(CardByYear other) {
    int byYear = Integer.compare(this.year, other.year);
    if (byYear != 0) { return byYear; }
    int byTitle = this.title.compareTo(other.title);
    if (byTitle != 0) { return byTitle; }
    return this.author.compareTo(other.author);   // all three fields: consistent with equals
}

Or, far more readably, with a Comparator (the next section):

private static final Comparator<CardByYear> ORDER =
    Comparator.comparingInt(CardByYear::year)
              .thenComparing(CardByYear::title)
              .thenComparing(CardByYear::author);

@Override
public int compareTo(CardByYear other) { return ORDER.compare(this, other); }

And the documentation advice: if your natural order is deliberately not consistent with equals, say so in the Javadoc. BigDecimal is the JDK's canonical example: new BigDecimal("1.0").equals(new BigDecimal("1.00")) is false but compareTo returns 0, and that is why a TreeSet<BigDecimal> behaves differently from a HashSet<BigDecimal>.

`Comparator`: external and multiple ordering

Comparator defines an ordering from outside the class, and it solves Comparable's two limitations: you can have as many as you like, and they work with classes you do not control.

public interface Comparator<T> {
    int compare(T a, T b);
}

It is a functional interface (04-06), so it accepts the three forms you already know:

// 1. An anonymous class: the classic form (04-04)
Comparator<Material> byTitle = new Comparator<Material>() {
    @Override public int compare(Material a, Material b) {
        return a.getTitle().compareTo(b.getTitle());
    }
};

// 2. A lambda (04-05)
Comparator<Material> byTitle2 = (a, b) -> a.getTitle().compareTo(b.getTitle());

// 3. Comparator.comparing with a method reference: the modern form (04-06)
Comparator<Material> byTitle3 = Comparator.comparing(Material::getTitle);

All three do the same. Always use the third: it is shorter, more readable and less error-prone, because you do not write the comparison by hand.

The catalogue of `Comparator` methods

We pick up and complete what was in 04-06.

Construction

Comparator.comparing(Material::getTitle)                     // by a Comparable key
Comparator.comparingInt(Loan::getLoanDay)                    // an int key: NO autoboxing
Comparator.comparingLong(LogEntry::getTimestamp)             // a long key
Comparator.comparingDouble(Material::getDailyRate)           // a double key
Comparator.naturalOrder()                                    // the type's natural order
Comparator.reverseOrder()                                    // the natural order reversed

Why comparingInt and not comparing. Comparator.comparing(Material::getLoanDays) works, but the extractor returns an int and the signature expects a Comparable, so every call does autoboxing: it creates an Integer per comparison. Sorting a million elements involves on the order of twenty million comparisons, and therefore forty million temporary objects. comparingInt accepts a ToIntFunction and compares primitives directly.

Rule: if the key is int, long or double, use the specialised variant.

Composition

Comparator<Material> criteria =
    Comparator.comparing(Material::getType)                   // first by type
              .thenComparing(Material::getTitle)              // on a tie, by title
              .thenComparingDouble(Material::getDailyRate);   // and then by rate

thenComparing is only consulted when the previous one returns 0. It is exactly the tie-breaking mechanism from section 4, written declaratively.

And it has specialised variants for the same reason as comparing: thenComparingInt, thenComparingLong, thenComparingDouble.

Reversal

Comparator<Material> expensiveFirst = Comparator.comparingDouble(Material::getDailyRate)
                                                .reversed();

Be careful where you put reversed(): it reverses everything composed up to that point, not just the last thing.

// Reverses BOTH criteria: type descending and, on a tie, title descending
Comparator.comparing(Material::getType)
          .thenComparing(Material::getTitle)
          .reversed();

// Reverses ONLY the title: type ascending, title descending
Comparator.comparing(Material::getType)
          .thenComparing(Material::getTitle, Comparator.reverseOrder());

The second form —thenComparing(extractor, keyComparator)— is the one you need when each criterion carries its own direction. It is a very frequent and silent mistake.

Nulls

Comparator<Material> safe    = Comparator.nullsFirst(Comparator.comparing(Material::getTitle));
Comparator<Material> atTheEnd = Comparator.nullsLast(Comparator.comparing(Material::getTitle));

nullsFirst and nullsLast wrap a comparator so that it accepts null elements, placing them at the beginning or at the end. Without them, a single null in the list throws NullPointerException in the middle of the sort.

And if what can be null is the key, not the element:

Comparator<Material> byAuthor = Comparator.comparing(
    m -> ((Book) m).getAuthor(),
    Comparator.nullsLast(Comparator.naturalOrder()));

Summary table

Method	What it does
`comparing(f)`	Sorts by the key that `f` extracts
`comparingInt/Long/Double(f)`	The same, with no autoboxing. Use them if the key is primitive
`thenComparing(f)`	A tie-break by another key
`thenComparing(f, cmp)`	A tie-break with its own direction
`reversed()`	Reverses everything accumulated up to there
`naturalOrder()` / `reverseOrder()`	The type's natural order, direct or reversed
`nullsFirst(cmp)` / `nullsLast(cmp)`	Tolerates `null` elements

Frequently used comparators are worth declaring as constants:

public final class MaterialOrders {
    public static final Comparator<Material> BY_TITLE =
        Comparator.comparing(Material::getTitle);
    public static final Comparator<Material> BY_TYPE_AND_TITLE =
        Comparator.comparing(Material::getType).thenComparing(Material::getTitle);
    public static final Comparator<Material> BY_RATE_DESC =
        Comparator.comparingDouble(Material::getDailyRate).reversed()
                  .thenComparing(Material::getReference);   // tie-break for a total order
    private MaterialOrders() { }
}

catalog.sort(MaterialOrders.BY_TYPE_AND_TITLE);

Besides being readable, it avoids creating a new comparator on every call.

The four sorting strategies

Strategy	How	Cost	When
`List.sort(cmp)`	In place, on the list	O(n log n)	By default with lists
`Collections.sort(list)`	In place, natural order	O(n log n)	Compatibility; prefer `List.sort`
`Arrays.sort(array)`	In place, on an array	O(n log n)	When you work with arrays
A sorted collection	It maintains itself	O(log n) per insertion	When the order must always hold

// 1. List.sort: the interface's own method. THE DEFAULT OPTION
catalog.sort(Comparator.comparing(Material::getTitle));
catalog.sort(null);                                     // natural order

// 2. Collections.sort: predates Java 8, does the same
Collections.sort(cards);                                // natural order
Collections.sort(catalog, Comparator.comparing(Material::getTitle));

// 3. Arrays.sort
Material[] array = catalog.toArray(new Material[0]);
Arrays.sort(array, Comparator.comparing(Material::getTitle));
Arrays.sort(array, 0, 10, comparator);                  // only a range

// 4. Collections that keep themselves sorted
TreeSet<Card> alwaysSorted = new TreeSet<>();            // by compareTo
TreeMap<String, Material> byKey = new TreeMap<>();       // sorted keys
PriorityQueue<Loan> byUrgency = new PriorityQueue<>(comparator);   // only the head

The criteria for choosing

The decisive question is how many times you are going to need the order:

Situation	Strategy
Sorting once for display	`List.sort`
Sorting by different criteria depending on the moment	`List.sort` with several comparators
The data must always be sorted and is consulted often	`TreeSet` / `TreeMap`
Range queries (`headSet`, `subMap`, `floorKey`)	`TreeSet` / `TreeMap`
You only need "the next most urgent one", never the full list	`PriorityQueue`
You insert many times and sort rarely	`ArrayList` + `sort` at the end
You insert rarely and query sorted many times	`TreeSet`

A cost analysis for n insertions:

ArrayList + sort at the end: n O(1) insertions + one O(n log n) sort = O(n log n) total.
TreeSet: n O(log n) insertions = O(n log n) total.

They are the same complexity, but the constants clearly favour the ArrayList: a sort over contiguous memory is much faster than n insertions into a tree with scattered nodes. If you only need the order at the end, ArrayList + sort wins. The TreeSet wins when the order must be available between insertions, or when you need its range operations.

Stability and sorting by successive criteria

A sort is stable if the elements that tie keep their original relative order.

List<Card> cards = new ArrayList<>(List.of(
    new Card("Refactoring",     "Martin Fowler", 1999),
    new Card("Effective Java",  "Joshua Bloch",  2018),
    new Card("Design Patterns", "Erich Gamma",   1994),
    new Card("Clean Code",      "Robert Martin", 2008)));

// First by author
cards.sort(Comparator.comparing(Card::author));
// Then by year
cards.sort(Comparator.comparingInt(Card::year));

With a stable sort, after the second sort the cards from the same year are still sorted by author. With an unstable one, that order would have been lost.

Java guarantees that Collections.sort, List.sort and Arrays.sort over objects are stable. Over primitives (int[], double[]) they are not, and it does not matter: two equal ints are indistinguishable, so stability is meaningless.

That guarantee enables the technique of sorting in successive passes: sorting by the least important criterion first and by the most important one last.

// Strategy A: successive passes (from the LEAST important criterion to the MOST important)
catalog.sort(Comparator.comparing(Material::getTitle));       // secondary
catalog.sort(Comparator.comparing(Material::getType));        // primary

// Strategy B: a composed comparator
catalog.sort(Comparator.comparing(Material::getType)
                       .thenComparing(Material::getTitle));

Both give the same result, but always prefer B: it makes a single pass instead of two, expresses the intent directly and does not rely on the reader remembering that the pass order is the reverse of the priority.

Strategy A is still useful in one case: interactive interfaces. When the user clicks "sort by type" on a table already sorted by title, stability makes the result "by type and, within each type, by title" —exactly what they expect— without the program having to remember the previous criterion.

Which algorithm Java really uses

Java uses two different algorithms, and the choice reveals an interesting design decision.

TimSort, for objects

Collections.sort, List.sort and Arrays.sort(Object[]) use TimSort, a hybrid algorithm created by Tim Peters for Python and adopted by Java 7.

Its central idea: real data is rarely completely unsorted. It usually contains already-sorted stretches —partially updated lists, data arriving almost in order, results of a previous sort—. TimSort detects those stretches, called runs, extends them and merges them.

It walks the array looking for already-sorted stretches (ascending or descending; descending ones it reverses).
If a stretch is short, it extends it with insertion sort, which is very fast on small stretches.
It merges the stretches in pairs, as in merge sort.

Case	Complexity
Best case (already sorted)	O(n)
Average case	O(n log n)
Worst case	O(n log n)
Extra memory	O(n)
Stable	Yes

That O(n) in the best case is its great virtue: re-sorting an almost sorted list is practically free.

TimSort is also what throws the famous IllegalArgumentException: Comparison method violates its general contract!. It is not a whim: while merging runs, the algorithm detects that the comparisons are inconsistent and prefers to fail rather than produce an incorrect result. If you see that error, your comparator violates the contract from section 2.

Dual-pivot quicksort, for primitives

Arrays.sort(int[]), Arrays.sort(double[]) and the rest use dual-pivot quicksort, a variant of quicksort with two pivots that splits the array into three parts instead of two.

Case	Complexity
Best and average	O(n log n)
Worst case	O(n²) (with adversarial input, very unlikely)
Extra memory	O(log n)
Stable	No

Why two algorithms

	Objects (TimSort)	Primitives (quicksort)
Cost of comparing	High: a call to `compareTo`/`compare`	Low: one CPU instruction
Cost of moving	High: moving references, touching the cache	Low: moving a value
Does stability matter?	Yes: two "equal" objects are distinguishable	No: two equal `int`s are identical
Extra memory	Acceptable	Minimal is preferred
Choice	TimSort: minimises comparisons, stable	Quicksort: in place, minimal memory

With objects, each comparison can be expensive and stability matters: TimSort minimises comparisons by exploiting the pre-existing order. With primitives, comparing is trivial, stability means nothing and what counts is not spending memory: quicksort sorts in place.

In practice you do not need to choose: Java does it for you. But knowing it explains two things you will see: why re-sorting an almost sorted list is so fast, and where that IllegalArgumentException comes from.

Searching: linear, binary and by key

Three strategies, three complexities and one clear criterion.

Linear search

Walking and comparing until you find it. It is what contains, indexOf and any loop of your own do.

boolean there = catalog.contains(material);          // O(n), uses equals
int position = catalog.indexOf(material);            // O(n)

Material found = null;                               // a search by criterion
for (Material m : catalog) {
    if (m.getReference().equals("978-0000000001")) { found = m; break; }
}

Advantages	Drawbacks
It requires no prior ordering	O(n)
It works with any criterion	It degrades with size
No extra memory

Binary search

Over a sorted collection: look at the middle element, discard the half that cannot contain it and repeat.

List<Card> cards = new ArrayList<>(...);
cards.sort(null);                                    // COMPULSORY to sort first

int pos = Collections.binarySearch(cards, wanted);
int pos2 = Collections.binarySearch(catalog, probe,
                                    Comparator.comparing(Material::getReference));

int pos3 = Arrays.binarySearch(array, wanted);

With a million elements, about 20 comparisons instead of a million.

Advantages	Drawbacks
O(log n)	It requires prior ordering by the same criterion
It returns the insertion point if it is absent	Sorting costs O(n log n)
No extra memory	Over a `LinkedList` it is O(n) because of the indexed access

That last point deserves attention: Collections.binarySearch checks whether the list implements RandomAccess (05-03). If it does not —the LinkedList case—, it switches to an iterator-based strategy, and the result is worse than a linear search. Binary search only over ArrayList or arrays.

Search by key

A hash-based Map or Set, as you saw in 05-05 and 05-06.

Map<String, Material> index = new HashMap<>();
Material m = index.get("978-0000000001");            // O(1)
boolean exists = references.contains("978-0000000001");   // O(1)

Advantages	Drawbacks
O(1)	Extra memory for the index
It requires no ordering	It requires correct `equals`/`hashCode`
It scales perfectly	It only works for the indexed key

Decision table

Situation	Strategy	Cost
You search once, a small collection	Linear	O(n)
You search by an arbitrary, changing criterion	Linear	O(n)
You search many times by the same key	`Map`/`Set`	O(1)
You need ordering and searches	`TreeMap`/`TreeSet`	O(log n)
The list is already sorted by that criterion	`binarySearch`	O(log n)
You search ranges ("everything between A and B")	`TreeSet.subSet`	O(log n) + the range size

And the practical rule: if you are going to search more than a few times by the same key, build an index. The cost of creating the HashMap (O(n), once) pays for itself almost immediately, as you saw in 05-06.

`binarySearch` and its negative value

Collections.binarySearch and Arrays.binarySearch return:

If they find it: the element's index, a value ≥ 0.
If they do not find it: -(insertion point) - 1, a negative value.

The insertion point is the position where the element would have to be inserted to keep the order.

List<Integer> sorted = new ArrayList<>(List.of(10, 20, 30, 40, 50));

System.out.println(Collections.binarySearch(sorted, 30));     //  2  (it is at index 2)
System.out.println(Collections.binarySearch(sorted, 35));     // -4  (it would go at index 3)
System.out.println(Collections.binarySearch(sorted, 5));      // -1  (it would go at index 0)
System.out.println(Collections.binarySearch(sorted, 99));     // -6  (it would go at index 5)

Why such an odd formula

Because index 0 is a valid "found" result, and -0 is 0: there would be no way of telling "it is at position 0" from "it would go at position 0". Subtracting one shifts all the negatives and removes the ambiguity.

To recover the insertion point:

int result = Collections.binarySearch(sorted, 35);
if (result >= 0) {
    System.out.println("Found at position " + result);
} else {
    int insertionPoint = -result - 1;                    // -(-4) - 1 = 3
    System.out.println("Not there; it would go at position " + insertionPoint);
    sorted.add(insertionPoint, 35);                      // an ordered insertion
}

This idiom —search, and if it is absent insert at the returned point— is the standard way of keeping a list sorted without re-sorting it every time.

The two indispensable conditions

1. The collection must be sorted. Over an unsorted one, the result is garbage, with no warning.

List<Integer> unsorted = new ArrayList<>(List.of(30, 10, 50, 20, 40));
System.out.println(Collections.binarySearch(unsorted, 50));      // -3, and 50 is right there

2. It must be sorted by the SAME criterion you search with. If you sort by title and search with a comparator by reference, the result makes no sense.

catalog.sort(Comparator.comparing(Material::getTitle));

// WRONG: sorted by title, searched by reference
Collections.binarySearch(catalog, probe, Comparator.comparing(Material::getReference));

// RIGHT: the same comparator in both
Comparator<Material> byTitle = Comparator.comparing(Material::getTitle);
catalog.sort(byTitle);
Collections.binarySearch(catalog, probe, byTitle);

A practical detail: binarySearch needs an element to compare with, not a loose key value. To search for "the material with reference X" you need a probe element, a dummy instance with that reference. It is awkward, and it is one more reason to prefer a Map when you search by key.

And a final warning: if there are duplicate elements according to the criterion, binarySearch returns any one of them, not necessarily the first.

`Collections` utilities

java.util.Collections is the Framework's utility class, sibling of Arrays. These are the ones still to be met:

List<Card> cards = new ArrayList<>(...);

// Extremes, with natural order or with a Comparator
Card first = Collections.min(cards);
Card last  = Collections.max(cards);
Material expensive = Collections.max(catalog, Comparator.comparingDouble(Material::getDailyRate));

// Counting occurrences (uses equals)
int howMany = Collections.frequency(catalog, effectiveJava);

// Modifying the list in place
Collections.reverse(cards);            // reverses the order. O(n)
Collections.shuffle(cards);            // shuffles randomly. O(n)
Collections.swap(cards, 0, 3);         // swaps two positions. O(1)
Collections.rotate(cards, 2);          // shifts 2 positions circularly
Collections.fill(cards, template);     // fills everything with the same element

// Creating
List<String> repeats = Collections.nCopies(3, "pending");   // an IMMUTABLE list of 3 equal items
Collections.addAll(catalog, m1, m2, m3);                    // adding several at once

// Querying
boolean unrelated = Collections.disjoint(withLoan, withOverdue);   // no common elements

// Views and special collections (05-02)
List<Material> readOnly = Collections.unmodifiableList(catalog);
List<Material> empty = Collections.emptyList();
List<Material> one = Collections.singletonList(effectiveJava);

Method	What it does	Cost
`min(c)` / `max(c)`	Extremes by natural order or `Comparator`	O(n)
`frequency(c, o)`	How many times it appears, using `equals`	O(n)
`reverse(l)`	Reverses the list in place	O(n)
`shuffle(l)`	Shuffles randomly	O(n)
`swap(l, i, j)`	Swaps two positions	O(1)
`rotate(l, d)`	Shifts circularly	O(n)
`nCopies(n, o)`	An immutable list of n copies	O(1)
`disjoint(a, b)`	Do they share no element?	O(n)
`addAll(c, e...)`	Adds several loose elements	O(n)

Two useful observations. min and max are O(n) and require no prior ordering: to find the maximum just once, they are better than sorting. And shuffle accepts a Random with a seed (Collections.shuffle(list, new Random(42))), which makes the shuffling reproducible, indispensable for tests.

Performance: sort once, search many times

The central trade-off of this lesson, with numbers.

Suppose a catalogue of 100,000 materials on which we do 10,000 searches by reference.

Strategy	Preparation cost	Cost per search	Total (operations)
Linear, unprepared	0	50,000 on average	500,000,000
Sort + binary	~1,700,000 (n log n)	~17 (log n)	~1,870,000
`HashMap` index	100,000 (n)	1	110,000

The lesson is twofold. Preparing the data pays off enormously as soon as there are several searches: sorting costs the same as 1.7 linear searches and saves all the rest. And the hash index beats binary search when you search by exact equality.

So when should you choose binary search over a HashMap?

When you need the ordering as well as the search.
When you search by range, not by exact value ("everything published between 1990 and 2000").
When memory is critical: a sorted ArrayList takes far less space than a HashMap.
When the key does not have a good hashCode.

And the break-even point, as a rough guide:

Expected searches	Recommended strategy
1-2	Linear: preparing does not pay off
3-100	Sort + binary, or an index
More than 100	`HashMap` index
Any number, but you also need ordering	`TreeMap`

And the usual warning: these figures are operations, not time. For 200 elements, every strategy is instantaneous and you should choose for clarity. Optimisation starts to matter from tens of thousands upwards.

Closing the module: the state of BiblioTech

Let us bring the complete project together with everything learned in the module.

package com.nexussoftware.bibliotech.service;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
import java.util.function.Predicate;
import com.nexussoftware.bibliotech.domain.*;

/** BiblioTech at the end of module 5: every structure in its place. */
public class BiblioTech {

    // --- Catalogue: a list for the order, maps for the indexes ---
    private final List<Material>              catalog     = new ArrayList<>();
    private final Map<String, Material>       byReference = new HashMap<>();
    private final Map<String, List<Material>> byType      = new HashMap<>();
    private final Set<String>                 seenIsbns   = new HashSet<>();

    // --- Loans ---
    private final Map<String, Loan>            loans      = new HashMap<>();
    private final Map<Employee, List<Loan>>    byEmployee = new HashMap<>();

    // --- Reservations: one FIFO queue per material ---
    private final Map<String, Deque<Reservation>> reservations = new HashMap<>();

    // --- Reversible history ---
    private final Deque<CatalogOperation> undo = new ArrayDeque<>();

    // --- Reusable comparators ---
    public static final Comparator<Material> BY_TITLE =
        Comparator.comparing(Material::getTitle);
    public static final Comparator<Material> BY_TYPE_AND_TITLE =
        Comparator.comparing(Material::getType).thenComparing(Material::getTitle);
    public static final Comparator<Material> BY_RATE_DESC =
        Comparator.comparingDouble(Material::getDailyRate).reversed()
                  .thenComparing(Material::getReference);       // tie-break: a TOTAL order

    // ---------- Catalogue ----------

    public boolean register(Material m, int day) {
        if (m == null || !seenIsbns.add(m.getReference())) { return false; }
        catalog.add(m);
        byReference.put(m.getReference(), m);
        byType.computeIfAbsent(m.getType(), t -> new ArrayList<>()).add(m);
        undo.push(new CatalogOperation(CatalogOperation.Type.ADD, m, day));
        return true;
    }

    public boolean deregister(String reference, int day) {
        Material m = byReference.remove(reference);
        if (m == null) { return false; }
        seenIsbns.remove(reference);
        catalog.remove(m);
        byType.computeIfPresent(m.getType(),
                (t, list) -> { list.remove(m); return list.isEmpty() ? null : list; });
        undo.push(new CatalogOperation(CatalogOperation.Type.REMOVE, m, day));
        return true;
    }

    /** Search by key: O(1). */
    public Material find(String reference) { return byReference.get(reference); }

    /** Search by an arbitrary criterion: O(n), unavoidable. */
    public List<Material> find(Predicate<Material> criteria) {
        List<Material> result = new ArrayList<>();
        for (Material m : catalog) {
            if (criteria.test(m)) { result.add(m); }
        }
        return result;
    }

    public List<Material> list(Comparator<Material> criteria) {
        List<Material> copy = new ArrayList<>(catalog);
        copy.sort(criteria);                        // TimSort, O(n log n), stable
        return copy;
    }

    // ---------- Loans ----------

    public boolean lend(String reference, Employee employee, int day) {
        Material m = byReference.get(reference);
        if (m == null || !m.isAvailable() || !employee.canBorrow()) {
            return false;
        }
        Loan l = new Loan(m, employee, day);
        loans.put(l.getReference(), l);
        byEmployee.computeIfAbsent(employee, e -> new ArrayList<>()).add(l);
        m.lend();
        employee.registerLoan();
        return true;
    }

    public boolean returnItem(String loanReference, int day) {
        Loan l = loans.get(loanReference);                    // O(1)
        if (l == null || l.isReturned()) { return false; }
        l.registerReturn(day);
        l.getEmployee().registerReturn();

        // Serve the material's first reservation, if there is one
        Deque<Reservation> queue = reservations.get(l.getMaterial().getReference());
        if (queue != null) {
            Reservation next = queue.pollFirst();
            if (next != null) {
                next.markFulfilled();
                System.out.printf("NOTICE: %s can collect '%s'%n",
                        next.getEmployee().getName(), l.getMaterial().getTitle());
            }
        }
        return true;
    }

    public void reserve(String reference, Employee employee, int day) {
        Material m = byReference.get(reference);
        if (m == null) { return; }
        reservations.computeIfAbsent(reference, r -> new ArrayDeque<>())
                    .offerLast(new Reservation(employee, m, day));
    }

    // ---------- Reports ----------

    /** Counters by type, in a TreeMap so that they always come out sorted. */
    public Map<String, Integer> reportByType() {
        Map<String, Integer> summary = new TreeMap<>();
        for (Material m : catalog) { summary.merge(m.getType(), 1, Integer::sum); }
        return summary;
    }

    /** A ranking of employees by accumulated fine, from highest to lowest. */
    public Map<Employee, Double> fineRanking(int currentDay) {
        Map<Employee, Double> fines = new HashMap<>();
        for (List<Loan> list : byEmployee.values()) {
            for (Loan l : list) {
                double fine = l.calculateFine(currentDay);
                if (fine > 0) { fines.merge(l.getEmployee(), fine, Double::sum); }
            }
        }
        // A map is NOT sorted by value: you have to dump, sort and rebuild
        List<Map.Entry<Employee, Double>> entries = new ArrayList<>(fines.entrySet());
        entries.sort(Map.Entry.<Employee, Double>comparingByValue().reversed());

        Map<Employee, Double> sorted = new LinkedHashMap<>();      // preserves the order
        for (Map.Entry<Employee, Double> e : entries) {
            sorted.put(e.getKey(), e.getValue());
        }
        return sorted;
    }

    /** The N most urgent loans, with a PriorityQueue. */
    public List<Loan> mostUrgent(int howMany, int currentDay) {
        Queue<Loan> queue = new PriorityQueue<>(
            Comparator.comparingDouble((Loan l) -> l.calculateFine(currentDay)).reversed()
                      .thenComparing(Loan::getReference));
        for (Loan l : loans.values()) {
            if (!l.isReturned() && l.isOverdue(currentDay)) { queue.offer(l); }
        }
        List<Loan> result = new ArrayList<>();
        for (int i = 0; i < howMany && !queue.isEmpty(); i++) {
            result.add(queue.poll());                // poll: the ONLY guaranteed order
        }
        return result;
    }

    /** The most expensive material: min/max are O(n), no need to sort. */
    public Material mostExpensive() {
        return catalog.isEmpty() ? null
             : Collections.max(catalog, Comparator.comparingDouble(Material::getDailyRate));
    }

    public CatalogOperation lastOperation() { return undo.peek(); }
    public int catalogSize() { return catalog.size(); }
}

And a complete session:

BiblioTech app = new BiblioTech();

Employee marta = new Employee("Marta Ruiz",   "EMP-001");
Employee diego = new Employee("Diego Alonso", "EMP-002");
Employee nuria = new Employee("Nuria Vidal",  "EMP-003");

app.register(new Book("Effective Java",  "Joshua Bloch",  "978-0000000001", 2018), 100);
app.register(new Book("Design Patterns", "Erich Gamma",   "978-0000000002", 1994), 100);
app.register(new Book("Refactoring",     "Martin Fowler", "978-0000000003", 1999), 100);
app.register(new Magazine("Java Magazine", "REV-2024-03", 42, "Monthly"),          101);
app.register(new Dvd("Refactoring Live", "DVD-0007",      95),                     101);

System.out.println("=== Catalogue by type and title ===");
app.list(BiblioTech.BY_TYPE_AND_TITLE)
   .forEach(m -> System.out.printf("  %-8s %-26s %.2f EUR/day%n",
           m.getType(), m.getTitle(), m.getDailyRate()));

app.lend("978-0000000001", marta, 100);
app.lend("978-0000000003", marta, 102);
app.lend("DVD-0007",       diego, 105);
app.reserve("978-0000000001", nuria, 106);        // Effective Java is on loan

System.out.println("\n=== Report by type ===");
app.reportByType().forEach((t, n) -> System.out.printf("  %-8s %d%n", t, n));

System.out.println("\n=== Most urgent loans (day 140) ===");
app.mostUrgent(3, 140).forEach(l -> System.out.printf("  %-16s %-26s %6.2f EUR%n",
        l.getEmployee().getName(), l.getMaterial().getTitle(), l.calculateFine(140)));

System.out.println("\n=== Fine ranking (day 140) ===");
app.fineRanking(140).forEach((e, fine) ->
        System.out.printf("  %-16s %6.2f EUR%n", e.getName(), fine));

System.out.println("\n=== Return with a pending reservation ===");
app.returnItem("LN-0001", 140);

System.out.println("\nMost expensive material: " + app.mostExpensive().getTitle());
System.out.println("Last operation:          " + app.lastOperation());

=== Catalogue by type and title ===
  Book     Design Patterns            0.25 EUR/day
  Book     Effective Java             0.25 EUR/day
  Book     Refactoring                0.25 EUR/day
  DVD      Refactoring Live           0.50 EUR/day
  Magazine Java Magazine              0.10 EUR/day

=== Report by type ===
  Book     3
  DVD      1
  Magazine 1

=== Most urgent loans (day 140) ===
  Diego Alonso     Refactoring Live            16.00 EUR
  Marta Ruiz       Effective Java               6.25 EUR
  Marta Ruiz       Refactoring                  5.75 EUR

=== Fine ranking (day 140) ===
  Diego Alonso      16.00 EUR
  Marta Ruiz        12.00 EUR

=== Return with a pending reservation ===
NOTICE: Nuria Vidal can collect 'Effective Java'

Most expensive material: Refactoring Live
Last operation:          Material added: 'Refactoring Live' (DVD-0007) on day 101

The balance sheet: what BiblioTech can do

Need	Structure	Cost
A sortable, traversable catalogue	`List<Material>` (`ArrayList`)	O(n) traversal, O(1) access
Search by reference	`Map<String, Material>`	O(1)
Grouping by type	`Map<String, List<Material>>` with `computeIfAbsent`	O(1)
Rejecting duplicate ISBNs	`Set<String>` with the `boolean` from `add`	O(1)
Loans by reference	`Map<String, Loan>`	O(1)
Loans by employee	`Map<Employee, List<Loan>>`	O(1)
A reservation queue per material	`Map<String, Deque<Reservation>>` (`ArrayDeque`)	O(1) at the ends
Notices by urgency	`PriorityQueue<Loan>`	O(log n)
Undo history	`Deque<CatalogOperation>` (`ArrayDeque`)	O(1)
Sorted reports	`TreeMap` / `LinkedHashMap`	O(log n) / O(1)
Sorting by any criterion	Composed `Comparator`s	O(n log n)

And that twenty-line reportByType with nested loops from module 4 has been reduced to, literally, three.

What is still fragile

And now the honest part. Look at any method in the project with a critical eye and you will see the same weakness:

1. Any invalid data breaks the program. Integer.parseInt("abc") throws NumberFormatException and the application ends. byReference.get(null) can give a NullPointerException. catalog.get(99) gives an IndexOutOfBoundsException. stack.pop() on an empty stack, NoSuchElementException. 1 / 0, ArithmeticException. Throughout the module we have carefully avoided those situations by checking first, but checking first is not always possible or sufficient.

2. Errors are reported by returning null or false. find(reference) returns null if it is absent: does it not exist, or was the reference invalid? register returns false: because of a duplicate, a null material, an empty reference? The return value cannot carry the reason for the failure, so the caller cannot react differently depending on the case.

3. Notices are printed to the console. The whole project is full of System.out.println("WARNING: ..."). That is not error handling: it is a message nobody can catch, log or handle. A service running without a console loses all that information.

4. A half-completed failure leaves the system inconsistent. If register adds to the ISBN Set and fails before adding to the list, the ISBN is marked as catalogued without the material existing. There is no way of partially undoing an operation.

5. Nothing is saved on exit. Everything lives in memory. Closing the program deletes the catalogue, the loans, the reservations and the history. The next run starts from scratch.

The first four points are exactly the syllabus of module 6. The fifth, that of module 7.

Common Mistakes and Tips

Subtracting to compare. a - b overflows with large integers and truncates with doubles. Use Integer.compare, Double.compare, and so on. No exceptions.

(int) (doubleA - doubleB). Every difference smaller than 1 is truncated to 0: different elements are declared equal. Double.compare, always.

An ordering not consistent with equals in a TreeSet or TreeMap. Elements that tie according to the comparator are considered the same one, and the second is discarded silently. Add tie-breaking criteria until the ordering is total.

Putting reversed() in the wrong place. It reverses everything composed up to that point, not just the last criterion. If each criterion carries its own direction, use thenComparing(extractor, Comparator.reverseOrder()).

Using comparing with primitive keys. It causes autoboxing on every comparison. comparingInt, comparingLong and comparingDouble exist precisely for that.

binarySearch over an unsorted collection. It returns meaningless results, with no warning. And it must be sorted by the same criterion you search with.

Interpreting binarySearch's negative as "-1, not there". It is -(insertion point) - 1. To get the point: -result - 1.

binarySearch over a LinkedList. Indexed access is O(n), so the "binary" search ends up worse than a linear one. Only over ArrayList or arrays.

Sorting to find the maximum. Collections.max is O(n); sorting is O(n log n). If you only need the extreme, do not sort.

Sorting a list inside a loop. It is the classic performance mistake: sort once outside, or use a TreeSet if the order must always hold.

Ignoring IllegalArgumentException: Comparison method violates its general contract! It is not a Java failure: it is TimSort telling you your comparator is inconsistent. Check transitivity and antisymmetry.

Tip: declare frequently used comparators as constants. They are immutable and reusable; creating a new one on every call is noise.

Tip: for a "top N", dump entrySet(), sort and rebuild into a LinkedHashMap. A map is never sorted by value, and only LinkedHashMap preserves the order you insert in.

Tip: if you search more than a few times by the same key, build an index. The HashMap pays for itself almost immediately.

Exercises

Exercise 1: a sortable catalogue with multiple criteria

Write SortableCatalog with an internal List<Material> and:

A nested class Orders with Comparator<Material> constants for: by title, by type and title, by rate descending, by availability and then title, and by type and rate descending.
List<Material> sortedBy(Comparator<Material>): returns a sorted copy, without touching the original.
void sortInPlace(Comparator<Material>).
Material max(Comparator<Material>) and Material min(Comparator<Material>) using Collections.
List<Material> topN(int n, Comparator<Material>).
int binarySearchByTitle(String title): sorts by title if necessary and correctly interprets the negative value, reporting the insertion point.

Every comparator must produce a total order (with a tie-break by reference).

Exercise 2: a demonstration of the broken contracts

Write OrderingDemo with a main that demonstrates, printing and explaining:

That subtracting integers overflows: compare a - b with Integer.compare(a, b) for extreme values.
That (int)(doubleA - doubleB) truncates BiblioTech's rates and declares them all equal.
That an ordering inconsistent with equals makes a TreeSet lose elements, while a HashSet does not.
That Java's sort is stable: sort by author, then by year, and check that within each year the order by author is preserved.
That reversed() reverses everything accumulated, with the correct way of reversing a single criterion.
That binarySearch over an unsorted list returns garbage.

Exercise 3: a comparison of search strategies

Write SearchStrategyComparison which, with 100,000 materials and 10,000 searches by reference, measures:

A linear search with a for over an ArrayList.
Sorting once + Collections.binarySearch with a probe element.
Building a HashMap once + get.
Building a TreeMap once + get.

Print a table with the preparation time, the search time and the total, and include the warning about JMH. Write a reasoned conclusion stating when you would choose each strategy.

Solutions

Solution 1

package com.nexussoftware.bibliotech.service;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import com.nexussoftware.bibliotech.domain.Book;
import com.nexussoftware.bibliotech.domain.Material;

public class SortableCatalog {

    private final List<Material> materials = new ArrayList<>();
    private Comparator<Material> currentOrder = null;   // remembers how it is sorted

    /** Reusable comparators. ALL of them end with a tie-break by reference. */
    public static final class Orders {
        private Orders() { }

        public static final Comparator<Material> BY_TITLE =
            Comparator.comparing(Material::getTitle)
                      .thenComparing(Material::getReference);

        public static final Comparator<Material> BY_TYPE_AND_TITLE =
            Comparator.comparing(Material::getType)
                      .thenComparing(Material::getTitle)
                      .thenComparing(Material::getReference);

        // comparingDouble: no autoboxing. reversed() before the tie-break,
        // so that the reference keeps sorting ASCENDING.
        public static final Comparator<Material> BY_RATE_DESC =
            Comparator.comparingDouble(Material::getDailyRate).reversed()
                      .thenComparing(Material::getReference);

        // Available first: false < true, so the boolean has to be inverted
        public static final Comparator<Material> BY_AVAILABILITY =
            Comparator.comparing((Material m) -> !m.isAvailable())
                      .thenComparing(Material::getTitle)
                      .thenComparing(Material::getReference);

        // Type ASCENDING, rate DESCENDING: each criterion with its own direction.
        // A .reversed() at the end would ALSO reverse the type: the classic mistake.
        public static final Comparator<Material> BY_TYPE_AND_RATE_DESC =
            Comparator.comparing(Material::getType)
                      .thenComparing(Material::getDailyRate, Comparator.reverseOrder())
                      .thenComparing(Material::getReference);
    }

    public void add(Material m) {
        if (m != null) { materials.add(m); currentOrder = null; }   // the order is lost
    }

    /** A sorted copy: the original catalogue keeps its order. */
    public List<Material> sortedBy(Comparator<Material> criteria) {
        List<Material> copy = new ArrayList<>(materials);
        copy.sort(criteria);
        return copy;
    }

    public void sortInPlace(Comparator<Material> criteria) {
        materials.sort(criteria);
        currentOrder = criteria;
    }

    /** max/min are O(n): far better than sorting (O(n log n)) for a single extreme. */
    public Material max(Comparator<Material> criteria) {
        return materials.isEmpty() ? null : Collections.max(materials, criteria);
    }

    public Material min(Comparator<Material> criteria) {
        return materials.isEmpty() ? null : Collections.min(materials, criteria);
    }

    public List<Material> topN(int n, Comparator<Material> criteria) {
        List<Material> sorted = sortedBy(criteria);
        return new ArrayList<>(sorted.subList(0, Math.min(n, sorted.size())));
    }

    /**
     * A binary search by title. It sorts only when necessary and uses
     * the SAME comparator to sort and to search: an indispensable requirement.
     */
    public int binarySearchByTitle(String title) {
        if (title == null) { return -1; }

        Comparator<Material> criteria = Orders.BY_TITLE;
        if (currentOrder != criteria) {
            sortInPlace(criteria);            // O(n log n), but only the first time
        }

        // binarySearch needs an ELEMENT, not a loose key: a probe is required.
        // It is a real drawback, and one more reason to prefer a Map (05-05).
        Material probe = new Book(title, "", "", 2000);
        int result = Collections.binarySearch(materials, probe,
                Comparator.comparing(Material::getTitle));    // only the title: the probe
                                                              // has no valid reference

        if (result >= 0) {
            System.out.printf("'%s' found at position %d%n", title, result);
        } else {
            int insertionPoint = -result - 1;         // the formula: -(pos) - 1
            System.out.printf("'%s' is not there; it would go at position %d%n", title, insertionPoint);
        }
        return result;
    }

    public int size() { return materials.size(); }
}

A test:

SortableCatalog c = new SortableCatalog();
c.add(new Book("Refactoring",     "Martin Fowler", "978-0000000003", 1999));
c.add(new Book("Effective Java",  "Joshua Bloch",  "978-0000000001", 2018));
c.add(new Magazine("Java Magazine", "REV-2024-03", 42, "Monthly"));
c.add(new Dvd("Refactoring Live", "DVD-0007",      95));
c.add(new Book("Design Patterns", "Erich Gamma",   "978-0000000002", 1994));

System.out.println("--- By type and rate descending ---");
c.sortedBy(SortableCatalog.Orders.BY_TYPE_AND_RATE_DESC)
 .forEach(m -> System.out.printf("  %-8s %-26s %.2f%n",
         m.getType(), m.getTitle(), m.getDailyRate()));

System.out.println("Most expensive: " + c.max(
        Comparator.comparingDouble(Material::getDailyRate)).getTitle());

System.out.println("--- Top 2 by rate ---");
c.topN(2, SortableCatalog.Orders.BY_RATE_DESC)
 .forEach(m -> System.out.println("  " + m.getTitle()));

c.binarySearchByTitle("Effective Java");
c.binarySearchByTitle("Clean Code");

Three important decisions. Every comparator ends with thenComparing(Material::getReference), which is unique, so the ordering is total and these comparators can be used in a TreeSet with no risk. In BY_TYPE_AND_RATE_DESC the direction is applied to each criterion separately with thenComparing(extractor, reverseOrder()), because a .reversed() at the end would have reversed the type as well. And binarySearchByTitle remembers the current order so as not to re-sort on every call, although the probe detail makes it clear why, for searching by key, a Map is nearly always better.

Solution 2

package com.nexussoftware.bibliotech.presentation;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class OrderingDemo {

    record SimpleCard(String title, String author, int year) { }

    /** A natural order INCONSISTENT with equals: it only looks at the year. */
    record CardByYear(String title, String author, int year)
            implements Comparable<CardByYear> {
        @Override public int compareTo(CardByYear o) { return Integer.compare(year, o.year); }
    }

    public static void main(String[] args) {
        overflow();
        truncation();
        inconsistency();
        stability();
        misplacedReversed();
        binarySearchUnsorted();
    }

    static void overflow() {
        System.out.println("=== 1. Subtracting integers OVERFLOWS ===");
        int a = 2_000_000_000, b = -2_000_000_000;

        System.out.println("a = " + a + ", b = " + b + "  -> a is clearly GREATER");
        System.out.println("a - b               = " + (a - b) + "   <- NEGATIVE: it says a < b");
        System.out.println("Integer.compare(a,b)= " + Integer.compare(a, b) + "   <- correct");
        System.out.println("Cause: 4,000,000,000 does not fit in an int (max 2,147,483,647),");
        System.out.println("the value wraps around and changes sign. Never subtract.\n");
    }

    static void truncation() {
        System.out.println("=== 2. Subtracting doubles and casting TRUNCATES ===");
        double book = 0.25, magazine = 0.10, dvd = 0.50;

        System.out.println("(int)(dvd - magazine)      = " + (int)(dvd - magazine)
                           + "   <- 0.40 truncated to 0: 'they are equal'");
        System.out.println("(int)(book - magazine)     = " + (int)(book - magazine) + "   <- likewise");
        System.out.println("Double.compare(dvd,magazine)= " + Double.compare(dvd, magazine));
        System.out.println("With this bug, ALL BiblioTech's rates would be equal");
        System.out.println("and the catalogue would not be sorted at all.\n");
    }

    static void inconsistency() {
        System.out.println("=== 3. An ordering inconsistent with equals ===");
        CardByYear a = new CardByYear("Effective Java",  "Joshua Bloch", 2018);
        CardByYear b = new CardByYear("Design Patterns", "Erich Gamma",  2018);

        System.out.println("a.equals(b):    " + a.equals(b)    + "   <- they are DIFFERENT");
        System.out.println("a.compareTo(b): " + a.compareTo(b) + "   <- but they TIE");

        System.out.println("In a List:     " + new ArrayList<>(List.of(a, b)).size() + " elements");
        System.out.println("In a HashSet:  " + new HashSet<>(List.of(a, b)).size()
                           + " elements   <- it uses equals/hashCode: correct");
        System.out.println("In a TreeSet:  " + new TreeSet<>(List.of(a, b)).size()
                           + " elements   <- it uses compareTo: ONE IS LOST");

        Set<CardByYear> fixed = new TreeSet<>(
            Comparator.comparingInt(CardByYear::year)
                      .thenComparing(CardByYear::title));      // a tie-break
        fixed.addAll(List.of(a, b));
        System.out.println("With a tie-break: " + fixed.size() + " elements   <- fixed\n");
    }

    static void stability() {
        System.out.println("=== 4. Java's sort is STABLE ===");
        List<SimpleCard> cards = new ArrayList<>(List.of(
            new SimpleCard("Refactoring",       "Martin Fowler", 1999),
            new SimpleCard("Clean Code",        "Robert Martin", 2008),
            new SimpleCard("Effective Java",    "Joshua Bloch",  2018),
            new SimpleCard("Java Concurrency",  "Brian Goetz",   2018),
            new SimpleCard("Design Patterns",   "Erich Gamma",   1999)));

        cards.sort(Comparator.comparing(SimpleCard::author));      // the SECONDARY criterion
        System.out.println("After sorting by author:");
        cards.forEach(c -> System.out.printf("  %-16s %d  %s%n", c.author(), c.year(), c.title()));

        cards.sort(Comparator.comparingInt(SimpleCard::year));     // the PRIMARY criterion
        System.out.println("After sorting by year (within each year, still by author):");
        cards.forEach(c -> System.out.printf("  %-16s %d  %s%n", c.author(), c.year(), c.title()));

        System.out.println("Prefer the composed comparator: ONE pass and clearer:");
        cards.sort(Comparator.comparingInt(SimpleCard::year)
                             .thenComparing(SimpleCard::author));
        System.out.println();
    }

    static void misplacedReversed() {
        System.out.println("=== 5. Where to put reversed() ===");
        List<SimpleCard> cards = new ArrayList<>(List.of(
            new SimpleCard("Effective Java",   "Joshua Bloch", 2018),
            new SimpleCard("Java Concurrency", "Brian Goetz",  2018),
            new SimpleCard("Refactoring",      "Martin Fowler", 1999)));

        List<SimpleCard> bad = new ArrayList<>(cards);
        bad.sort(Comparator.comparingInt(SimpleCard::year)
                           .thenComparing(SimpleCard::author)
                           .reversed());          // reverses YEAR AND AUTHOR
        System.out.println("With .reversed() at the end (it reverses BOTH):");
        bad.forEach(c -> System.out.printf("  %d %s%n", c.year(), c.author()));

        List<SimpleCard> good = new ArrayList<>(cards);
        good.sort(Comparator.comparingInt(SimpleCard::year).reversed()
                            .thenComparing(SimpleCard::author));   // only the year
        System.out.println("With .reversed() after the year (it only reverses the year):");
        good.forEach(c -> System.out.printf("  %d %s%n", c.year(), c.author()));
        System.out.println();
    }

    static void binarySearchUnsorted() {
        System.out.println("=== 6. binarySearch over an UNSORTED list ===");
        List<Integer> unsorted = new ArrayList<>(List.of(30, 10, 50, 20, 40));
        System.out.println("List: " + unsorted);
        System.out.println("binarySearch(50): " + java.util.Collections.binarySearch(unsorted, 50)
                           + "   <- 50 IS at index 2, but it returns a negative");

        List<Integer> sorted = new ArrayList<>(unsorted);
        java.util.Collections.sort(sorted);
        System.out.println("Sorted: " + sorted);
        System.out.println("binarySearch(50): " + java.util.Collections.binarySearch(sorted, 50)
                           + "   <- correct");
        System.out.println("binarySearch(35): " + java.util.Collections.binarySearch(sorted, 35)
                           + "   <- -(insertion point) - 1 = -(3) - 1");
        System.out.println("Insertion point: "
                           + (-java.util.Collections.binarySearch(sorted, 35) - 1));
    }
}

The six parts share one trait: none of them throws an exception. The overflow returns a number, the truncation returns zero, the TreeSet loses an element without complaint, the misplaced reversed() sorts "something" and binarySearch returns a plausible negative. Ordering and comparison errors are silent, and that is why it pays to know the contracts: there is no compiler and no exception to warn you.

Solution 3

package com.nexussoftware.bibliotech.presentation;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import com.nexussoftware.bibliotech.domain.Book;
import com.nexussoftware.bibliotech.domain.Material;

/**
 * Compares four search-by-reference strategies.
 *
 * WARNING: this is not a rigorous benchmark. The JIT compiles on the fly,
 * the collector can step in and the compiler can remove code whose result
 * is not used. To measure seriously, JMH (05-04). These figures are only
 * good for seeing ORDERS OF MAGNITUDE.
 */
public class SearchStrategyComparison {

    private static final int N        = 100_000;
    private static final int SEARCHES = 10_000;
    private static long shield = 0;      // stops the JIT removing the loops

    public static void main(String[] args) {
        List<Material> catalog = generate(N);
        List<String>   keys    = randomKeys(SEARCHES);

        System.out.println("Warming up the JVM...");
        for (int i = 0; i < 3; i++) {
            linear(catalog.subList(0, 1000), keys.subList(0, 100));
            withHashMap(catalog.subList(0, 1000), keys.subList(0, 100));
        }

        System.out.printf("%n=== %d materials, %d searches ===%n", N, SEARCHES);
        System.out.printf("%-24s %12s %12s %12s%n",
                          "Strategy", "Prepare", "Search", "TOTAL");
        System.out.println("-".repeat(64));

        long[] r1 = linear(catalog, keys);
        long[] r2 = withBinary(catalog, keys);
        long[] r3 = withHashMap(catalog, keys);
        long[] r4 = withTreeMap(catalog, keys);

        row("1. Linear (for + equals)", r1);
        row("2. Sort + binarySearch",   r2);
        row("3. HashMap",               r3);
        row("4. TreeMap",               r4);

        System.out.println("\n(shield = " + shield + ", ignore it)");
        conclusion();
    }

    private static void row(String label, long[] t) {
        System.out.printf("%-24s %9d ms %9d ms %9d ms%n", label, t[0], t[1], t[0] + t[1]);
    }

    /** 1. Linear: no preparation, O(n) per search. */
    private static long[] linear(List<Material> catalog, List<String> keys) {
        long t = System.nanoTime();
        int found = 0;
        for (String key : keys) {
            for (Material m : catalog) {
                if (m.getReference().equals(key)) { found++; break; }
            }
        }
        shield += found;
        return new long[]{ 0, ms(t) };
    }

    /** 2. Sort once, O(n log n), then O(log n) per search. */
    private static long[] withBinary(List<Material> catalog, List<String> keys) {
        Comparator<Material> byReference = Comparator.comparing(Material::getReference);

        long t1 = System.nanoTime();
        List<Material> sorted = new ArrayList<>(catalog);
        sorted.sort(byReference);
        long prepare = ms(t1);

        long t2 = System.nanoTime();
        int found = 0;
        for (String key : keys) {
            // binarySearch needs an ELEMENT: a probe has to be built per search.
            // That extra cost is real and penalises this strategy.
            Material probe = new Book("", "", key, 2000);
            if (Collections.binarySearch(sorted, probe, byReference) >= 0) { found++; }
        }
        shield += found;
        return new long[]{ prepare, ms(t2) };
    }

    /** 3. A hash index: O(n) to build, O(1) per search. */
    private static long[] withHashMap(List<Material> catalog, List<String> keys) {
        long t1 = System.nanoTime();
        Map<String, Material> index = new HashMap<>((int)(catalog.size() / 0.75f) + 1);
        for (Material m : catalog) { index.put(m.getReference(), m); }
        long prepare = ms(t1);

        long t2 = System.nanoTime();
        int found = 0;
        for (String key : keys) {
            if (index.get(key) != null) { found++; }
        }
        shield += found;
        return new long[]{ prepare, ms(t2) };
    }

    /** 4. A tree: O(n log n) to build, O(log n) per search, but SORTED. */
    private static long[] withTreeMap(List<Material> catalog, List<String> keys) {
        long t1 = System.nanoTime();
        Map<String, Material> index = new TreeMap<>();
        for (Material m : catalog) { index.put(m.getReference(), m); }
        long prepare = ms(t1);

        long t2 = System.nanoTime();
        int found = 0;
        for (String key : keys) {
            if (index.get(key) != null) { found++; }
        }
        shield += found;
        return new long[]{ prepare, ms(t2) };
    }

    private static List<Material> generate(int n) {
        List<Material> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new Book("Title " + i, "Author " + (i % 500),
                              String.format("978-%010d", i), 1990 + (i % 35)));
        }
        return list;
    }

    private static List<String> randomKeys(int howMany) {
        List<String> keys = new ArrayList<>(howMany);
        java.util.Random random = new java.util.Random(42);    // a fixed seed: reproducible
        for (int i = 0; i < howMany; i++) {
            keys.add(String.format("978-%010d", random.nextInt(N)));
        }
        return keys;
    }

    private static long ms(long startNano) {
        return (System.nanoTime() - startNano) / 1_000_000;
    }

    private static void conclusion() {
        System.out.println("""

            === Conclusion ===
            1. LINEAR: zero preparation, but every search walks half the list.
               With 10,000 searches over 100,000 elements that is about 500 million
               comparisons. It is only worth it for 1-2 searches or small lists.

            2. SORT + BINARY: the preparation is the most expensive (O(n log n)) and each
               search is O(log n), about 17 comparisons. Besides, a PROBE element has to be
               built per search, which penalises it quite a lot.
               It is worth it when you also need the list sorted.

            3. HASHMAP: O(n) preparation and O(1) search. It is by far the fastest
               and the default answer for searching by an exact key.
               The price: extra memory and needing correct equals/hashCode.

            4. TREEMAP: O(n log n) preparation and O(log n) search. Slower than
               the HashMap, but in exchange it keeps the keys SORTED and offers
               firstKey, headMap, floorKey and range queries.

            CRITERIA:
              - You search 1-2 times  ............ linear
              - You search by exact key, often ... HashMap
              - You need ordering or ranges ...... TreeMap
              - The list is already sorted ....... binarySearch
            """);
    }
}

Typical output:

=== 100000 materials, 10000 searches ===
Strategy                      Prepare       Search        TOTAL
----------------------------------------------------------------
1. Linear (for + equals)         0 ms      2840 ms      2840 ms
2. Sort + binarySearch           95 ms        42 ms       137 ms
3. HashMap                       18 ms         2 ms        20 ms
4. TreeMap                       78 ms         9 ms        87 ms

The numbers confirm the analysis in section 13, with one additional lesson: preparation is almost always worth it. The linear one takes 2840 ms with no preparation at all; the HashMap takes 20 ms including building the index. Preparing costs 18 ms and saves 2820.

And there is a nuance the theoretical tables do not show: strategy 2 comes out worse than its O(log n) would suggest, because it builds a probe object on every search. That cost does not appear in the asymptotic analysis and yet it dominates the real time. It is a reminder that O() describes how an operation scales, not how much it costs to run: to decide for real, you have to measure.

Conclusion

You have closed the module with the operations that cut across every collection. You know that Comparable defines a class's natural order through compareTo, whose sign —negative, zero, positive— is the only thing that matters, and you know its complete contract: antisymmetry, transitivity, consistency, consistency with equals and the rejection of null. You know that breaking it produces incorrect sorts or the IllegalArgumentException: Comparison method violates its general contract! that TimSort throws when it detects the inconsistency.

You have memorised the mistake most present in production code: never subtract to compare. a - b overflows with large integers and returns the opposite sign; (int)(doubleA - doubleB) truncates any difference smaller than 1 and declares different elements equal. The answer is always Integer.compare, Double.compare and their siblings. And you understand why consistency with equals matters so much: TreeSet and TreeMap decide uniqueness with compareTo, not with equals, so a partial ordering loses elements silently. The solution is to add tie-breaks until the ordering is total.

You have mastered Comparator in its modern form: comparing, the comparingInt/Long/Double variants that avoid autoboxing, thenComparing for the tie-breaks, reversed() —with the warning that it reverses everything accumulated, and thenComparing(extractor, reverseOrder()) when each criterion needs its own direction— and nullsFirst/nullsLast to tolerate absent elements. And you know how to declare them as reusable constants.

You know the four sorting strategies and the criterion that decides between them —how many times you need the order—, with the practical conclusion that ArrayList + sort wins when the order is only needed at the end and TreeSet/TreeMap win when it must be available between insertions or there are range queries. You understand stability and why it allows sorting by successive criteria —although a composed comparator is preferable—, and you know what lies underneath: TimSort for objects, hybrid, stable and O(n) when the data is already almost sorted; dual-pivot quicksort for primitives, in place and with minimal memory. And you know why they are two different algorithms.

In searching, you have the three strategies with their complexities and their criteria: linear when you search rarely or by changing criteria; binary when the collection is already sorted by the same criterion —with the exact interpretation of the negative as -(insertion point) - 1 and the warning not to use it over a LinkedList—; and by key in a Map or Set when you search many times for the same thing. You have seen with numbers that preparing the data almost always pays off: building a HashMap costs the same as a few linear searches and saves all the rest. And you know the Collections utilities that were still missing: max, min, frequency, reverse, shuffle, swap, rotate, nCopies, disjoint and addAll.

BiblioTech, at the close of module 5, is a real management system. Its catalogue is a List<Material> sortable by any Comparator, backed by a Map<String, Material> that finds any material by its reference in constant time, a Map<String, List<Material>> that groups by type built with computeIfAbsent, and a Set<String> that rejects duplicate ISBNs relying only on the boolean returned by add. Loans are indexed by reference and by employee, fines accumulate with merge, each material's reservations wait in a FIFO ArrayDeque that serves itself on return, notices come out of a PriorityQueue that serves the most urgent one first, and a Deque<CatalogOperation> allows the last registration or removal to be cancelled. The reports by type and the fine ranking are generated in a single pass. And that twenty-line reportByType with nested loops that was promised a reduction to three, has ended up at three. There is not a single line of manual memory management left in the whole project.

And yet the project is fragile in a way that can no longer be ignored. The whole module has carefully dodged the problem: every method checks before acting, returns null or false when something goes wrong and prints System.out.println("WARNING: ...") for everything else. But checking first is not always possible. An Integer.parseInt("twenty") throws NumberFormatException and the application ends. An index out of range, a pop() on an empty stack, a division by zero, a file that does not exist: any of them stops the program dead. A returned false does not say why it failed, so the caller cannot react differently depending on the reason. A message printed to the console cannot be caught, logged or handled. And if an operation fails halfway —the ISBN is already in the Set but the material is not yet in the list—, the system is left inconsistent with no way back. Besides, none of this survives the program closing: everything lives in memory and the next run starts from scratch.

In module 6, Exception Handling, the first of these is solved. You will see what an exception really is and how it travels up the call stack you met in 05-08; the Throwable → Error/Exception → RuntimeException hierarchy and the distinction between checked and unchecked; the try-catch block with multiple catches and their compulsory order; throw to signal a failure and throws to declare it; custom exceptions that say exactly what went wrong —MaterialNotFoundException, DuplicateReferenceException, LoanLimitExceededException— and carry the error's data instead of a mute false; the finally block and the try-with-resources that releases resources for you; and the professional strategies for error handling and logging, so that BiblioTech's notices stop being System.out.println and become records that can be filtered, archived and analysed. By the end of it, BiblioTech will stop falling over at the first unexpected piece of data and will start behaving like software that goes into production.

Sorting and Searching Collections

Contents

Natural order with Comparable

The compareTo contract

The mistake of subtracting integers

Consistency with equals and what breaks without it

Comparator: external and multiple ordering

The catalogue of Comparator methods