Linear search is the simplest search algorithm, which checks the elements of an array or list one by one from the start and returns the index of the first element that matches the target, or -1 when no element matches. It works on any data, sorted or not, and takes O(n) time.
Linear search suits small or unsorted collections, for one-off lookups, and when the match condition is more than plain equality, such as the first order above a price. In Java, List.indexOf() and List.contains() already run a linear search for us.
The following example finds a book ID on a shelf with the linearSearch() method from section 2.
int[] shelf = {14, 7, 30, 21, 9};
int position = linearSearch(shelf, 21); // 3
int absent = linearSearch(shelf, 50); // -1The method returns an index, not a message, so the caller decides what to do with it. The trace comes first, followed by versions for objects and conditions, the JDK methods that do the same job, and a comparison with binary search and hash lookups.
1. How Linear Search Works
Linear search starts at index 0, compares each element with the target and moves to the next index until it finds a match or reaches the end. It needs no preparation, which is its main advantage over faster searches that need sorted data or a hash table.
In our example, the search compares 14, 7, 30 and 21 with the target and finds the match at index 3 after four comparisons. Searching for 50 compares all five elements and returns -1.
2. Linear Search Program in Java
The method loops over the array and returns as soon as it finds the target. A loop that completes without a match means the target is missing, so the method returns -1, the same convention that String.indexOf() and List.indexOf() use. All the versions are in the Core-Java repository with a Java 25 demo.
static int linearSearch(int[] a, int target) {
if (a == null) {
return -1;
}
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
return i; // first match wins
}
}
return -1; // not found
}int[] codes = {5, 8, 5, 2};
int firstFive = linearSearch(codes, 5); // 0, the first of two matches
int nothing = linearSearch(null, 5); // -1
int none = linearSearch(new int[0], 5); // -1With duplicates, the method returns the first match. To find the last match, we loop from the end, as List.lastIndexOf() does.
2.1. Searching Strings and Objects
For objects, we compare with Objects.equals() instead of ==. The == operator compares references, so two different String objects with the same text would not match. Objects.equals() also handles null on either side.
static <T> int linearSearch(T[] a, T target) {
if (a == null) {
return -1;
}
for (int i = 0; i < a.length; i++) {
if (Objects.equals(a[i], target)) {
return i;
}
}
return -1;
}String[] cities = {"Pune", null, "Delhi"};
int delhi = linearSearch(cities, new String("Delhi")); // 2
int nullSlot = linearSearch(cities, null); // 12.2. Searching by a Condition
Linear search can test any condition, which binary search and jump search cannot do for arbitrary conditions. Say an online shop that shows the first product under a price limit, and the products are sorted by popularity, not by price.
record Product(String name, int price) {}static <T> int findFirst(List<T> items, Predicate<? super T> condition) {
for (int i = 0; i < items.size(); i++) {
if (condition.test(items.get(i))) {
return i;
}
}
return -1;
}List<Product> products = List.of(new Product("lamp", 40), new Product("mug", 12), new Product("rug", 9));
int cheap = findFirst(products, p -> p.price() < 15); // 1
int free = findFirst(products, p -> p.price() == 0); // -13. Linear Search with the Java API
In application code, we rarely write the loop ourselves, because the collection classes already contain it.
- List.indexOf() returns the index of the first element that equals the target, or -1, and List.contains() returns a boolean.
- Arrays.asList(array).indexOf(target) searches an object array without copying it.
- IntStream.range() with filter() and findFirst() searches a primitive array by index and returns an OptionalInt.
- Stream.filter().findFirst() returns the matching element itself as an Optional.
List<String> fruits = List.of("apple", "banana", "kiwi");
int kiwiIndex = fruits.indexOf("kiwi"); // 2
boolean hasPear = fruits.contains("pear"); // false
int[] ids = {14, 7, 30, 21, 9};
OptionalInt idx = IntStream.range(0, ids.length).filter(i -> ids[i] == 30).findFirst(); // OptionalInt[2]
Optional<String> longName = fruits.stream().filter(f -> f.length() > 5).findFirst(); // Optional[banana]All of these are O(n), the same as our loop. The streams read well for conditions, whereas indexOf() is the shortest choice for a plain equality search.
4. Linear Search Time Complexity
The number of comparisons depends on where the target is. If every position is equally likely, a successful search checks about half of the elements on average, and an unsuccessful search always checks all of them.
| Case | Comparisons | Time |
|---|---|---|
| Best (target at index 0) | 1 | O(1) |
| Average (target found) | about (n + 1)/2 | O(n) |
| Worst (target last or missing) | n | O(n) |
Linear search needs O(1) extra memory. On a sorted array of 10 million integers, one search took about 1.3 ms on average in our Java 25 test, whereas jump search took 4 to 10 microseconds and Arrays.binarySearch() under 1 microsecond.
5. Linear Search vs Binary Search vs HashSet
Linear search is the right choice when we search once, or when the data is small or unsorted; for repeated lookups in large data, sorting once or building a hash set is cheaper overall. The table summarizes the trade-offs.
| Approach | Needs | Lookup time | Best fit |
|---|---|---|---|
| Linear search | Nothing | O(n) | Small or unsorted data, conditions, one-off searches |
| Binary search | Sorted array | O(log n) | Large sorted arrays, range queries |
| Jump search | Sorted array | O(√n) | Sorted data where jumping back is costly |
| HashSet / HashMap | Building the set, O(n) once | O(1) on average | Many lookups in the same data |
For example, checking 1,000 user names against a list of 100,000 blocked names with linear search makes up to 100 million comparisons. Putting the blocked names into a HashSet once makes each check a single hash lookup.
6. Linear Search FAQs
Sorting, the -1 convention and small arrays come up after the first linear search program.
6.1. Does linear search need a sorted array?
No. It checks every element in order, so the order of the data does not matter. That is the main difference from binary search and jump search, which return wrong results on unsorted input.
6.2. Why does linear search return -1 when the element is not found?
Because -1 can never be a valid array index. It is the same convention as String.indexOf() and List.indexOf(), so callers can check index >= 0, or we return an OptionalInt when we want to make the missing case explicit.
6.3. How do we search in a 2D array?
We use two nested loops and return both indexes, for example as an int[] of row and column. The time is O(rows x columns), because every cell may need a check.
6.4. Is linear search faster than binary search for small arrays?
Often, yes. For a few dozen elements, a linear scan reads memory in order and the CPU predicts its branches well, whereas binary search jumps around and mispredicts about half of its branches. The difference only matters in tight loops.
7. Conclusion
Linear search compares the elements one by one and returns the index of the first match or -1. It needs no sorted data, works with any condition, and takes O(n) time with O(1) memory.
In Java code, List.indexOf(), contains() and streams with findFirst() do the same work. When the same large data is searched many times, a sorted array with binary search or a HashSet is much faster.
8. References
Happy Learning !!
