Java LinkedList binarySearch: comparisons are not the whole cost

The Java 8 program below compiles without external libraries; its output is checked against a real run.

Sort under the same ordering

The search contract requires ascending order under the same comparison used by the search. The fixture finds twenty at position one. Thirty is absent, so the negative result encodes insertion point two. Decode a negative result as -result-1, not as an array position to index directly.

If equal values occur several times, the returned matching index is not specified to be the first duplicate. A range lookup needs a separate lower-bound policy.

Choose a structure for repeated reads

For a large non-RandomAccess list, the JDK uses iterator-based search with O(n) link traversals and O(log n) comparisons. A small fixture cannot measure that cost. If the workload needs repeated random-access binary searches, an ArrayList or primitive array may better fit; if it needs key lookup, consider a map.

Working program

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
public class SortedReceiptCodeLookup {
    public static void main(String[] args) {
        LinkedList<Integer> codes = new LinkedList<>(Arrays.asList(10, 20, 40));
        int found = Collections.binarySearch(codes, 20);
        int missing = Collections.binarySearch(codes, 30);
        System.out.println("found=" + found);
        System.out.println("missing=" + missing + ", insert=" + (-missing - 1));
    }
}

Output

found=1
missing=-3, insert=2

Costs and boundaries

For a large LinkedList, the API documents O(n) link traversals and O(log n) comparisons. The index returned is a position, not a constant-time path to that node for later get(index) calls.

Common Mistakes

• Do not search an unsorted list and interpret the result.
• Do not promise O(log n) total work solely from the algorithm's name.
• Do not assume the first equal element is returned.

Read next

Java LinkedList: operations, internals and failure cases, Java LinkedList indexed loops: a hidden quadratic traversal, Java ArrayList and indexed access, Java HashMap: keys, collisions, and update operations.