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 The first match: findFirst and Optional Yes or no, and positions Smallest, largest, and lookup by key Short-circuiting and Optional traps How fast is each kind of lookup? Binary search: the return value and its rules The last match, and findAny in parallel Which method to use
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:
| Question | Method | Since | Returns |
|---|---|---|---|
| Is this exact value present? | list.contains(x) | Java 1.2 | boolean |
| Does any element match a condition? | stream().anyMatch(p) | Java 8 | boolean |
| Do all, or none, match? | allMatch(p)noneMatch(p) | Java 8 | boolean |
| Which is the first match? | filter(p).findFirst() | Java 8 | Optional<T> |
| Any match, in parallel | filter(p).findAny() | Java 8 | Optional<T> |
| Where is it? | indexOf(x)lastIndexOf(x) | Java 1.2 | Index or -1 |
| Smallest or largest by some order | stream().min(cmp)Collections.max | Java 8, 1.2 | Optional |
| First or last element | getFirst()getLast() | Java 21 | Element |
| Repeated lookups by key | A HashMap | Java 1.2 | Value or null |
The examples were run with JDK 21. To keep all matches rather than find one, see
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.
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:
first in data: Ben
first in mobile present? false
first in mobile: nobody
orElseThrow: no mobile engineer
found Ben, age 41
returns anfilter(...).findFirst() , because there may be no match.Optional turns either case into a value.map(Employee::name).orElse("nobody") reports whether something was found; for the mobile team it wasisPresent() .false is the right choice when a missing element means a bug or bad input, and it lets you choose the exception and message.orElseThrow(...) runs one action when a match exists and another when it does not, which avoids anifPresentOrElse onif followed byisPresent() . A plain loop withget() does the same search and can be clearer when the loop has more work to do.break
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.
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:
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
compares withcontains ;equals takes any condition. Both stop at the first hit.anyMatch stops at the first element that fails andallMatch at the first that matches.noneMatch has no shortcut and visits everything.count found the first 25 at index 2 andindexOf the last at 5; a missing value gives -1. To find the position of the first element matching a condition, anlastIndexOf over the indexes works, here giving 3.IntStream- On an empty list,
isallMatch andtrue isanyMatch . "Every element is positive" is true when there are no elements, which is logically correct but surprises people writing validation code.false
Smallest, largest, and lookup by key
Products with prices and codes cover the two other common searches: by an order, and by an identifier.
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:
cheapest: Mouse
priciest: Screen
M-2 -> Mouse
S-3 -> Screen
X-9 -> unknown
andmin 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).max- When the same list is searched by code again and again, building a
from code to product once turns each search into a hash lookup.Map handles unknown codes such asgetOrDefault . TheX-9list to map page shows how to build it.
Short-circuiting and Optional traps
The program uses peek
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:
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
andanyMatch 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.findFirst on an empty result throwsOptional.get() with "No value present". PreferNoSuchElementException ,orElse ororElseThrow , which make the empty case explicit.ifPresentOrElse cannot represent afindFirst element, because annull cannot holdOptional , so a list starting withnull made it thrownull . Filter out nulls first.NullPointerException andgetFirst() , new in Java 21, read the ends directly.getLast() found a differentcontains object with the same values, because records implementPoint by content. For classes withoutequals , only the same instance would be found.equals
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.
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):
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.
on a sorted list of IDs needs about 18 comparisons per lookup and was hundreds of times faster than the scan in every run.binarySearch- A
lookup was faster still. Building the map costs one pass over the list, which pays for itself after a handful of lookups.HashMap
Binary search: the return value and its rules
Collections.binarySearch
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"));
}
}
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
: -4 for 35, which means 35 belongs at index 3. The extra-(insertion point) - 1 lets a missing key that belongs at index 0 return -1 instead of 0, which would look like a hit.- 1 - 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
kept the list sorted, ending as-pos - 1 . Each insert still shifts the later elements, so for many inserts a[5, 10, 20, 30, 35, 40, 50, 99] is cheaper.TreeSet - On the unsorted list
, 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.[40, 10, 50, 20, 30] - With five 7s in a row, the search returned index 3, while
gave the first 7 at index 1. The documentation promises no particular one of several equal elements.indexOf - A list sorted by length had to be searched with the same length comparator, which found
at index 2. Searching it with natural order returned -1, because the halving steps assumed alphabetical order.apple
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 findFirstfindAny
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);
}
}
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,
searches from the end without copying the list, andlog.reversed().stream() on it found the later error, event 4. Before Java 21 the usual tool was a loop counting down fromfindFirst .size() - 1 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.IntStream.iterate- Parallel
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 usefindAny only when every match is equally acceptable.findAny - Parallel
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 whyfindFirst can be faster in parallel.findAny
Which method to use
| You want | Use |
|---|---|
| Is a value in the list? | list.contains(value) |
| Does anything match a condition? | list.stream().anyMatch(condition) |
| The first match, which may be missing | filter(condition).findFirst()orElse |
| The first match, which must exist | findFirst().orElseThrow(...) |
| The position of a value | indexOflastIndexOf |
| The smallest or largest | stream().min(cmp)max(cmp) |
| Many lookups by ID | Build a HashMap |
| Many lookups in sorted data | Collections.binarySearch |