Topic 45 of 78
Linear Search
Overview
Linear Search is the simplest, most intuitive searching algorithm in existence. You start at the beginning of an array or list and check each element one by one until you find what you are looking for (or reach the end). While it has a slow O(N) Time Complexity, it is the ONLY searching algorithm you can use if your data is completely unsorted or stored in a linked list.
Syntax
The logic is incredibly simple, but if `arr` has 10 million elements, and the target is at the very end, this loop runs 10 million times.
Basic Linear Search
java
public int linearSearch(int[] arr, int target) {
// Iterate through every single element
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Found it! Return the index.
}
}
return -1; // Exhausted the array, target not found
}Common Pitfalls
- Using Linear Search on massive datasets (Millions of rows) that could be sorted and searched using Binary Search.
- Off-by-one errors when using a manual `while` loop instead of a `for` loop.
Interview Tips
- Linear search is slow O(N), but it is the ONLY option if the data is unsorted or stored in a basic Linked List.
Real-World Example
Looking through a small, unsorted list of recently uploaded files to see if a specific filename exists.
example
java
public boolean doesFileExist(List<String> recentFiles, String targetFile) {
// Under the hood, List.contains() uses a Linear Search!
return recentFiles.contains(targetFile);
}