Find an Element in a List

Finding something in a list can mean several things: the first element that matches, whether any element matches, where an element is, or the smallest or largest one. Each question has its own method, and a lookup that is repeated should usually not be a list search at all. This page covers each kind of search, the Optional results and their traps, and how much faster an index or a map is.

Contents

Kinds of search, and what they cost

A list has no index other than position, so every search by content is a linear scan: the elements are checked one by one from the start until the answer is known. On average that is half the list for a successful search and the whole list for an unsuccessful one. The stream versions do the same scan; they read differently but do not search faster.

Searches answer different questions, and choosing the method that matches the question makes code shorter and lets the scan stop early:

Search methods for lists
QuestionMethodSinceReturns
Is this exact value present?list.contains(x)Java 1.2boolean
Does any element match a condition?stream().anyMatch(p)Java 8boolean
Do all, or none, match?allMatch(p), noneMatch(p)Java 8boolean
Which is the first match?filter(p).findFirst()Java 8Optional<T>
Any match, in parallelfilter(p).findAny()Java 8Optional<T>
Where is it?indexOf(x), lastIndexOf(x)Java 1.2Index or -1
Smallest or largest by some orderstream().min(cmp), Collections.maxJava 8, 1.2Optional, element
First or last elementgetFirst(), getLast()Java 21Element
Repeated lookups by keyA HashMap built onceJava 1.2Value or null

The examples were run with JDK 21. To keep all matches rather than find one, see filtering a list.

The first match: findFirst and Optional

The employee list has matches for the data team and none for the mobile team, so both outcomes of a search appear.

Java
import java.util.List;
import java.util.Optional;

public class FindOne {

    record Employee(String name, String team, int age) {
    }

    public static void main(String[] args) {
        List<Employee> staff = List.of(
                new Employee("Asha", "web", 29),
                new Employee("Ben", "data", 41),
                new Employee("Chen", "data", 35),
                new Employee("Dana", "ops", 52));

        // findFirst returns an Optional: there may be no match
        Optional<Employee> firstData = staff.stream()
                .filter(e -> e.team().equals("data"))
                .findFirst();
        System.out.println("first in data: " + firstData.map(Employee::name).orElse("nobody"));

        Optional<Employee> mobile = staff.stream()
                .filter(e -> e.team().equals("mobile"))
                .findFirst();
        System.out.println("first in mobile present? " + mobile.isPresent());
        System.out.println("first in mobile: " + mobile.map(Employee::name).orElse("nobody"));

        // orElseThrow when a missing match is a bug, not a normal case
        try {
            mobile.orElseThrow(() -> new IllegalStateException("no mobile engineer"));
        } catch (IllegalStateException e) {
            System.out.println("orElseThrow: " + e.getMessage());
        }

        // ifPresentOrElse runs one branch or the other
        firstData.ifPresentOrElse(
                e -> System.out.println("found " + e.name() + ", age " + e.age()),
                () -> System.out.println("not found"));
    }
}

Output:

Output
first in data: Ben
first in mobile present? false
first in mobile: nobody
orElseThrow: no mobile engineer
found Ben, age 41
  • filter(...).findFirst() returns an Optional, because there may be no match. map(Employee::name).orElse("nobody") turns either case into a value.
  • isPresent() reports whether something was found; for the mobile team it was false.
  • orElseThrow(...) is the right choice when a missing element means a bug or bad input, and it lets you choose the exception and message.
  • ifPresentOrElse runs one action when a match exists and another when it does not, which avoids an if on isPresent() followed by get(). A plain loop with break does the same search and can be clearer when the loop has more work to do.

Yes or no, and positions

A list of numbers with a repeated 25 shows the difference between first and last positions, and an empty list shows the edge case of the match methods.

Java
import java.util.List;
import java.util.stream.IntStream;

public class YesNoAndPosition {

    public static void main(String[] args) {
        List<Integer> readings = List.of(12, 17, 25, 9, 31, 25);

        System.out.println("contains 25?        " + readings.contains(25));
        System.out.println("anyMatch > 30?      " + readings.stream().anyMatch(r -> r > 30));
        System.out.println("allMatch > 5?       " + readings.stream().allMatch(r -> r > 5));
        System.out.println("noneMatch negative? " + readings.stream().noneMatch(r -> r < 0));
        System.out.println("count > 15:         " + readings.stream().filter(r -> r > 15).count());

        System.out.println("indexOf 25:         " + readings.indexOf(25));
        System.out.println("lastIndexOf 25:     " + readings.lastIndexOf(25));
        System.out.println("indexOf 99:         " + readings.indexOf(99));

        // Index of the first element matching a condition
        int firstBelow10 = IntStream.range(0, readings.size())
                .filter(i -> readings.get(i) < 10)
                .findFirst()
                .orElse(-1);
        System.out.println("first index < 10:   " + firstBelow10);

        // An empty stream: allMatch is true, anyMatch is false
        List<Integer> none = List.of();
        System.out.println("empty allMatch:     " + none.stream().allMatch(r -> r > 1000));
        System.out.println("empty anyMatch:     " + none.stream().anyMatch(r -> r > 1000));
    }
}

Output:

Output
contains 25?        true
anyMatch > 30?      true
allMatch > 5?       true
noneMatch negative? true
count > 15:         4
indexOf 25:         2
lastIndexOf 25:     5
indexOf 99:         -1
first index < 10:   3
empty allMatch:     true
empty anyMatch:     false
  • contains compares with equals; anyMatch takes any condition. Both stop at the first hit.
  • allMatch stops at the first element that fails and noneMatch at the first that matches. count has no shortcut and visits everything.
  • indexOf found the first 25 at index 2 and lastIndexOf the last at 5; a missing value gives -1. To find the position of the first element matching a condition, an IntStream over the indexes works, here giving 3.
  • On an empty list, allMatch is true and anyMatch is false. "Every element is positive" is true when there are no elements, which is logically correct but surprises people writing validation code.

Smallest, largest, and lookup by key

Products with prices and codes cover the two other common searches: by an order, and by an identifier.

Java
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class MinMaxAndLookup {

    record Product(String sku, String name, double price) {
    }

    public static void main(String[] args) {
        List<Product> catalog = List.of(
                new Product("K-1", "Keyboard", 49.0),
                new Product("M-2", "Mouse", 19.5),
                new Product("S-3", "Screen", 189.0));

        Product cheapest = catalog.stream()
                .min(Comparator.comparingDouble(Product::price))
                .orElseThrow();
        System.out.println("cheapest: " + cheapest.name());

        Product priciest = catalog.stream()
                .max(Comparator.comparingDouble(Product::price))
                .orElseThrow();
        System.out.println("priciest: " + priciest.name());

        // Many lookups by key: build a map once instead of searching the list each time
        Map<String, Product> bySku = catalog.stream()
                .collect(Collectors.toMap(Product::sku, Function.identity()));
        for (String sku : List.of("M-2", "S-3", "X-9")) {
            Product p = bySku.get(sku);
            System.out.println(sku + " -> " + (p == null ? "unknown" : p.name()));
        }
    }
}

Output:

Output
cheapest: Mouse
priciest: Screen
M-2 -> Mouse
S-3 -> Screen
X-9 -> unknown
  • min and max with a comparator find the cheapest and most expensive product in one pass, without sorting. Sorting just to take the first element costs O(n log n) instead of O(n).
  • When the same list is searched by code again and again, building a Map from code to product once turns each search into a hash lookup. getOrDefault handles unknown codes such as X-9. The list to map page shows how to build it.

Short-circuiting and Optional traps

The program uses peek to record which elements a stream actually examined, and then triggers the three exceptions that searches commonly produce.

Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Optional;

public class FindPitfalls {

    public static void main(String[] args) {
        List<Integer> nums = List.of(4, 8, 15, 16, 23, 42);

        // Streams stop as soon as the answer is known: peek shows what was examined
        List<Integer> seen = new ArrayList<>();
        boolean found = nums.stream().peek(seen::add).anyMatch(n -> n > 10);
        System.out.println("anyMatch(> 10) = " + found + ", examined " + seen);
        seen.clear();
        Optional<Integer> firstOdd = nums.stream().peek(seen::add).filter(n -> n % 2 == 1)
            .findFirst();
        System.out.println("findFirst odd  = " + firstOdd.orElseThrow() + ", examined " + seen);

        // Optional.get() on an empty result throws; use orElse, orElseThrow or ifPresent
        Optional<Integer> none = nums.stream().filter(n -> n > 100).findFirst();
        try {
            none.get();
        } catch (NoSuchElementException e) {
            System.out.println("get() on empty: NoSuchElementException: " + e.getMessage());
        }
        none.ifPresentOrElse(n -> System.out.println("found " + n),
            () -> System.out.println("ifPresentOrElse: nothing above 100"));

        // findFirst cannot return a null element: it throws instead
        List<String> withNull = Arrays.asList(null, "b");
        try {
            withNull.stream().findFirst();
        } catch (NullPointerException e) {
            System.out.println("findFirst on a null element: NullPointerException");
        }

        // Java 21: getFirst/getLast for the ends, without streams
        System.out.println("getFirst=" + nums.getFirst() + ", getLast=" + nums.getLast());

        // contains uses equals: a record with the same values is found
        record Point(int x, int y) {
        }
        List<Point> points = List.of(new Point(1, 2), new Point(3, 4));
        System.out.println("contains(new Point(3, 4)) = " + points.contains(new Point(3, 4)));
    }
}

Output:

Output
anyMatch(> 10) = true, examined [4, 8, 15]
findFirst odd  = 15, examined [4, 8, 15]
get() on empty: NoSuchElementException: No value present
ifPresentOrElse: nothing above 100
findFirst on a null element: NullPointerException
getFirst=4, getLast=42
contains(new Point(3, 4)) = true
  • anyMatch and findFirst examined only 4, 8 and 15 and never looked at the rest. Streams are lazy, so a search costs only as much as it needs.
  • Optional.get() on an empty result throws NoSuchElementException with "No value present". Prefer orElse, orElseThrow or ifPresentOrElse, which make the empty case explicit.
  • findFirst cannot represent a null element, because an Optional cannot hold null, so a list starting with null made it throw NullPointerException. Filter out nulls first.
  • getFirst() and getLast(), new in Java 21, read the ends directly.
  • contains found a different Point object with the same values, because records implement equals by content. For classes without equals, only the same instance would be found.

How fast is each kind of lookup?

The program looks up 500 random IDs among 200,000 users four ways, about a third of which exist, keeping the fastest of three runs.

Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.function.IntPredicate;

public class FindSpeed {

    record User(int id, String name) {
    }

    public static void main(String[] args) {
        int n = 200_000;
        List<User> users = new ArrayList<>(n);
        List<Integer> ids = new ArrayList<>(n);
        Map<Integer, User> byId = new HashMap<>();
        for (int i = 0; i < n; i++) {
            User u = new User(i * 3, "u" + i);
            users.add(u);
            ids.add(u.id());
            byId.put(u.id(), u);
        }
        int[] probes = new Random(2).ints(500, 0, 3 * n).toArray();
        System.out.printf("500 lookups by id among %,d users%n", n);
        time("for loop", probes, id -> {
            for (User u : users) {
                if (u.id() == id) {
                    return true;
                }
            }
            return false;
        });
        time("stream filter().findFirst()", probes,
            id -> users.stream().filter(u -> u.id() == id).findFirst().isPresent());
        time("binarySearch on sorted ids", probes, id -> Collections.binarySearch(ids, id) >= 0);
        time("HashMap.get", probes, id -> byId.get(id) != null);
    }

    // Best of 3 runs
    static void time(String name, int[] probes, IntPredicate find) {
        long best = Long.MAX_VALUE;
        int hits = 0;
        for (int run = 0; run < 3; run++) {
            hits = 0;
            long t0 = System.nanoTime();
            for (int p : probes) {
                if (find.test(p)) {
                    hits++;
                }
            }
            best = Math.min(best, System.nanoTime() - t0);
        }
        System.out.printf("  %-30s %9.2f ms  (%d found)%n", name, best / 1e6, hits);
    }
}

Output (rough timings on a 2-CPU Linux machine, JDK 21):

Output
500 lookups by id among 200,000 users
  for loop                          261.93 ms  (165 found)
  stream filter().findFirst()       398.86 ms  (165 found)
  binarySearch on sorted ids          0.63 ms  (165 found)
  HashMap.get                         0.08 ms  (165 found)
  • The loop and the stream both scan the list for every lookup, and most IDs are missing, so most lookups scan all 200,000 users. The stream was somewhat slower than the loop, but both took hundreds of milliseconds for just 500 lookups.
  • binarySearch on a sorted list of IDs needs about 18 comparisons per lookup and was hundreds of times faster than the scan in every run.
  • A HashMap lookup was faster still. Building the map costs one pass over the list, which pays for itself after a handful of lookups.

Binary search: the return value and its rules

Collections.binarySearch is the fast search for a sorted list, about 18 comparisons for 200,000 elements in the timing above. It is also the search with the most rules, and breaking any of them gives a wrong answer rather than an exception. The program walks through each rule.

Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class BinarySearchRules {

    public static void main(String[] args) {
        List<Integer> sorted = List.of(10, 20, 30, 40, 50);

        // 1. A found key returns its index; a missing key returns -(insertion point) - 1
        System.out.println("search 30: " + Collections.binarySearch(sorted, 30));
        int r = Collections.binarySearch(sorted, 35);
        System.out.println("search 35: " + r + ", insertion point " + (-r - 1));
        System.out.println("search 5:  " + Collections.binarySearch(sorted, 5)
            + ", search 99: " + Collections.binarySearch(sorted, 99));

        // 2. Insert at the insertion point to keep a list sorted
        List<Integer> growing = new ArrayList<>(sorted);
        for (int x : List.of(35, 5, 99)) {
            int pos = Collections.binarySearch(growing, x);
            growing.add(pos < 0 ? -pos - 1 : pos, x);
        }
        System.out.println("after sorted inserts: " + growing);

        // 3. On an unsorted list the answer is simply wrong, with no exception
        List<Integer> unsorted = List.of(40, 10, 50, 20, 30);
        System.out.println("unsorted, search 10: " + Collections.binarySearch(unsorted, 10)
            + " although indexOf(10) is " + unsorted.indexOf(10));

        // 4. With duplicates, any matching index may come back
        List<Integer> dups = List.of(1, 7, 7, 7, 7, 7, 9);
        System.out.println("duplicates, search 7: index " + Collections.binarySearch(dups, 7)
            + " (first 7 is at " + dups.indexOf(7) + ")");

        // 5. The comparator must be the one the list was sorted with
        List<String> byLength = new ArrayList<>(List.of("kiwi", "fig", "banana", "apple"));
        Comparator<String> len = Comparator.comparingInt(String::length);
        byLength.sort(len);
        System.out.println(byLength + ": with the length comparator "
            + Collections.binarySearch(byLength, "apple", len)
            + ", with natural order " + Collections.binarySearch(byLength, "apple"));
    }
}
Output
search 30: 2
search 35: -4, insertion point 3
search 5:  -1, search 99: -6
after sorted inserts: [5, 10, 20, 30, 35, 40, 50, 99]
unsorted, search 10: -1 although indexOf(10) is 1
duplicates, search 7: index 3 (first 7 is at 1)
[fig, kiwi, apple, banana]: with the length comparator 2, with natural order -1
  • A found key returns its index, 2 for 30. A missing key returns -(insertion point) - 1: -4 for 35, which means 35 belongs at index 3. The extra - 1 lets a missing key that belongs at index 0 return -1 instead of 0, which would look like a hit.
  • The ends follow the same formula: 5 gave -1, because it would go first, and 99 gave -6, past the last of five elements.
  • Inserting each new value at -pos - 1 kept the list sorted, ending as [5, 10, 20, 30, 35, 40, 50, 99]. Each insert still shifts the later elements, so for many inserts a TreeSet is cheaper.
  • On the unsorted list [40, 10, 50, 20, 30], the search for 10 returned -1, "not found", although 10 sits at index 1. The method does not check that the list is sorted, since checking would cost as much as the scan it replaces.
  • With five 7s in a row, the search returned index 3, while indexOf gave the first 7 at index 1. The documentation promises no particular one of several equal elements.
  • A list sorted by length had to be searched with the same length comparator, which found apple at index 2. Searching it with natural order returned -1, because the halving steps assumed alphabetical order.

The last match, and findAny in parallel

Most searches want the first match, but logs and histories often need the latest one. And parallel streams add a choice between findFirst and findAny.

Java
import java.util.List;
import java.util.Optional;
import java.util.stream.IntStream;

public class LastAndAny {

    record Event(int id, String type) {
    }

    public static void main(String[] args) {
        List<Event> log = List.of(new Event(1, "login"), new Event(2, "error"),
            new Event(3, "save"), new Event(4, "error"), new Event(5, "logout"));

        // The last match: Java 21 reversed() view, or an index loop from the end
        Optional<Event> lastError = log.reversed().stream()
            .filter(e -> e.type().equals("error")).findFirst();
        System.out.println("last error via reversed(): " + lastError.orElseThrow());
        int idx = IntStream.iterate(log.size() - 1, i -> i >= 0, i -> i - 1)
            .filter(i -> log.get(i).type().equals("error")).findFirst().orElse(-1);
        System.out.println("its index, searching backwards: " + idx);

        // findAny on a parallel stream may return any match, not the first
        List<Integer> nums = IntStream.range(0, 1_000_000).boxed().toList();
        java.util.Set<Integer> answers = new java.util.TreeSet<>();
        for (int run = 0; run < 20; run++) {
            answers.add(nums.parallelStream().filter(n -> n % 100_000 == 7).findAny()
                .orElseThrow());
        }
        int first = nums.parallelStream().filter(n -> n % 100_000 == 7).findFirst()
            .orElseThrow();
        System.out.println("parallel findAny, 20 runs, distinct answers: " + answers);
        System.out.println("parallel findFirst: " + first);
    }
}
Output
last error via reversed(): Event[id=4, type=error]
its index, searching backwards: 3
parallel findAny, 20 runs, distinct answers: [300007, 500007]
parallel findFirst: 7
  • Since Java 21, log.reversed().stream() searches from the end without copying the list, and findFirst on it found the later error, event 4. Before Java 21 the usual tool was a loop counting down from size() - 1.
  • IntStream.iterate with a condition (Java 9) counted the indexes down from the end and returned index 3, for searches that need the position rather than the element.
  • Parallel findAny never returned 7, the first match, in any of the 20 runs. The stream split the range into parts for its threads, and the answers listed came from whichever later part reported a match first. Across builds of this page the set of answers changed, from a single value to several, so use findAny only when every match is equally acceptable.
  • Parallel findFirst returned 7, the match closest to the start. It has to wait for the earlier parts of the stream to finish before it can answer, which is why findAny can be faster in parallel.

Which method to use

Choosing a search
You wantUse
Is a value in the list?list.contains(value)
Does anything match a condition?list.stream().anyMatch(condition)
The first match, which may be missingfilter(condition).findFirst() with orElse
The first match, which must existfindFirst().orElseThrow(...)
The position of a valueindexOf or lastIndexOf
The smallest or largeststream().min(cmp) or max(cmp), not sorting
Many lookups by IDBuild a HashMap once
Many lookups in sorted dataCollections.binarySearch