Linear Search
Overview
Linear Search is the simplest and most intuitive searching algorithm. To find a specific element in an array or list, you simply start at the beginning (index 0) and check every single element one by one until you find the target, or until you reach the end of the collection.
Because it checks every element sequentially, it does not require the data to be sorted. This makes it highly versatile. It works on unsorted arrays, Linked Lists, and any data structure that allows sequential iteration.
However, its simplicity is its weakness. In the worst-case scenario (the target is the very last element, or doesn't exist at all), you must check every single item. For a collection of 10 million items, that means 10 million checks. Therefore, its time complexity is strictly O(N).
Syntax
public class LinearSearch {
// Returns the index of the target, or -1 if not found
public static int search(int[] arr, int target) {
// Iterate through the entire array
for (int i = 0; i < arr.length; i++) {
// Check if current element matches the target
if (arr[i] == target) {
return i; // Found it! Return the index.
}
}
// If the loop finishes without returning, it's not here
return -1;
}
public static void main(String[] args) {
int[] data = {45, 12, 89, 33, 7};
int index = search(data, 33);
System.out.println("Found at index: " + index); // Output: 3
}
}Common Pitfalls
- Using Linear Search on massive datasets when the data is already sorted. If you know the array is sorted, using a Linear Search is a massive waste of processing power. You should always use Binary Search (O(log N)) for sorted data.
- Returning boolean
falseinstead of-1when searching for indices. A common beginner mistake is mixing up search functions that return the existence of an item (boolean) with functions that return the location of an item (integer). If returning an index, always use-1to represent 'not found', as0is a valid index. - Comparing Objects using
==instead of.equals(). If your array contains Strings or custom objects,if (arr[i] == target)will check for memory reference equality, not value equality. This will fail silently. Always useif (arr[i].equals(target))for objects.
Interview Questions
Best Case: O(1) if the target is the very first element. Worst Case: O(N) if the target is the very last element or not in the array. Average Case: O(N/2), which mathematically simplifies to O(N).
Yes, absolutely. Since a Linked List only supports sequential access anyway, traversing from head to tail node-by-node is the only way to search it. The time complexity remains O(N).
Real-World Example
When a teacher scans a messy, unalphabetized stack of test papers looking for 'John Doe', they are performing a physical linear search. They must check every paper one by one. In software, searching a small, unsorted configuration file for a specific key-value pair uses linear search.
public String findConfigValue(List<ConfigOption> config, String targetKey) {
// The config list is small and unsorted
for (ConfigOption option : config) {
if (option.key.equals(targetKey)) {
return option.value;
}
}
return "DEFAULT_VALUE";
}Check Your Knowledge
Test your understanding of Linear Search with these quick questions.