Imagine your friend hands you a shuffled deck of exam answer sheets and asks you to find the sheet with roll number 27.
The sheets are not in any order. So what do you do?
You pick up the first sheet and check it. Not 27? Put it aside and check the next one. You keep going one by one until you either find roll number 27 or run out of sheets.
That simple, natural strategy is called Linear Search.
It is the very first searching algorithm every programmer learns, and even though it is simple, it shows up everywhere: in interview questions, inside library methods like indexOf(), and as a building block for more complex algorithms.
What is Linear Search?
Linear Search is a searching algorithm that checks every element of a collection one by one, from start to end, until the target element is found or the collection ends.
It is also called Sequential Search, because it goes through the elements in sequence.
The idea in one line:
Start at the first element → compare → move to the next → repeatThe algorithm gives back:
The index of the element if it is found
-1if the element is not present (because-1can never be a valid array index)
You already saw a small version of this in the Arrays chapter when we checked whether a value exists in an array. In this chapter we will study it properly: how it works, its variations, its complexity and where it is the right (and wrong) choice.
How Linear Search Works
Let's say we have this array:
Index: 0 1 2 3 4 5
Value: 14 7 32 9 21 5We want to find 9.
Step 1
Index 0 → 14
14 == 9 ? No → move aheadStep 2
Index 1 → 7
7 == 9 ? No → move aheadStep 3
Index 2 → 32
32 == 9 ? No → move aheadStep 4
Index 3 → 9
9 == 9 ? Yes → Found at index 3We stop as soon as we find the element. We do not look at indexes 4 and 5.
Now suppose we search for 50:
14 → no
7 → no
32 → no
9 → no
21 → no
5 → no
Reached the end → return -1When the element is missing, we are forced to check every single element before we can say "not found".
The Algorithm
Written as simple steps:
1. Start from index 0.
2. Compare the current element with the target.
3. If they are equal, return the current index.
4. Otherwise, move to the next index.
5. If you reach the end of the array, return -1.Notice that there is no requirement for the array to be sorted. Linear search works on any order of data.
Linear Search in Java
class Main {
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // found it, return the index
}
}
return -1; // checked everything, not found
}
public static void main(String[] args) {
int[] numbers = {14, 7, 32, 9, 21, 5};
System.out.println("Index of 9: " + linearSearch(numbers, 9));
System.out.println("Index of 14: " + linearSearch(numbers, 14));
System.out.println("Index of 50: " + linearSearch(numbers, 50));
}
}Output:
Index of 9: 3
Index of 14: 0
Index of 50: -1Two details are worth noticing:
return iis inside the loop. The moment we find the target, we leave the method.return -1is after the loop. We only reach it when the loop has checked every element without success.
Counting the Comparisons
To really understand the cost of linear search, let's count how many comparisons it makes for different targets.
class Main {
static int comparisons = 0;
static int linearSearch(int[] arr, int target) {
comparisons = 0;
for (int i = 0; i < arr.length; i++) {
comparisons++;
if (arr[i] == target) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {8, 3, 6, 1, 9};
int[] targets = {8, 1, 9, 4};
for (int t : targets) {
int index = linearSearch(arr, t);
System.out.println("Target " + t + " -> index " + index
+ ", comparisons = " + comparisons);
}
}
}Output:
Target 8 -> index 0, comparisons = 1
Target 1 -> index 3, comparisons = 4
Target 9 -> index 4, comparisons = 5
Target 4 -> index -1, comparisons = 5This small experiment shows the three cases very clearly:
Target at the front → only 1 comparison
Target at the end →
ncomparisonsTarget missing → also
ncomparisons
Time and Space Complexity
Let n be the number of elements.
Best Case — O(1)
The target is the very first element. We make just one comparison.
[8, 3, 6, 1, 9] search 8
↑
found immediatelyWorst Case — O(n)
The target is the last element, or it is not present at all. We must check all n elements.
[8, 3, 6, 1, 9] search 4
↑ ↑ ↑ ↑ ↑
checked everything → not foundAverage Case — O(n)
If the target is equally likely to be at any position, on average we check about half the array:
(1 + 2 + 3 + ... + n) / n = (n + 1) / 2That is roughly n/2 comparisons. As we learned in the Time Complexity chapter, we drop constants, so n/2 is still O(n).
Space Complexity — O(1)
The iterative version uses only a loop variable, no matter how big the array is. So the extra space is constant.
Case | Comparisons | Time |
|---|---|---|
Best | 1 | O(1) |
Average | about n/2 | O(n) |
Worst | n | O(n) |
Extra space | — | O(1) |
Using the notations from the Big O, Big Ω & Big Θ chapter, linear search is O(n) in the worst case and Ω(1) in the best case.
Variations of Linear Search
In real problems, "find the element" can mean many different things. The good news is that all of them are small changes to the same loop.
1. First Occurrence
The basic version already returns the first index where the target appears, because it scans from the left and stops at the first match.
2. Last Occurrence
Scan from the right end instead:
static int lastIndex(int[] arr, int target) {
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] == target) {
return i;
}
}
return -1;
}3. Count Occurrences
Here we must not stop at the first match. We go through the whole array and count:
static int countOccurrences(int[] arr, int target) {
int count = 0;
for (int value : arr) {
if (value == target) {
count++;
}
}
return count;
}This always takes O(n), even in the best case, because we can't know whether more matches exist until we reach the end.
4. All Indexes
Same idea, but we store every matching index in a list:
static List<Integer> allIndexes(int[] arr, int target) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
result.add(i);
}
}
return result;
}5. Searching Strings
For objects such as String, compare with equals(), not ==. (We discussed why in the Strings chapter: == compares references, equals() compares content.)
static int searchName(String[] names, String target) {
for (int i = 0; i < names.length; i++) {
if (names[i].equals(target)) {
return i;
}
}
return -1;
}6. Recursive Linear Search
Using what we learned in the Recursion chapter, we can also write linear search recursively. There are two base cases: we ran out of elements, or we found the target.
static int searchRecursive(int[] arr, int target, int index) {
if (index == arr.length) {
return -1; // base case: nothing left
}
if (arr[index] == target) {
return index; // base case: found
}
return searchRecursive(arr, target, index + 1);
}This is a nice recursion exercise, but in practice the loop version is better. The recursive version uses O(n) stack space and can cause a StackOverflowError on very large arrays.
A Complete Example
Let's put all these variations together in one program:
import java.util.ArrayList;
import java.util.List;
class Main {
// Index of the first occurrence, or -1
static int firstIndex(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
// Index of the last occurrence, or -1
static int lastIndex(int[] arr, int target) {
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
// How many times target appears
static int countOccurrences(int[] arr, int target) {
int count = 0;
for (int value : arr) {
if (value == target) {
count++;
}
}
return count;
}
// Every index where target appears
static List<Integer> allIndexes(int[] arr, int target) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
result.add(i);
}
}
return result;
}
// Search in an array of Strings
static int searchName(String[] names, String target) {
for (int i = 0; i < names.length; i++) {
if (names[i].equals(target)) {
return i;
}
}
return -1;
}
// Recursive linear search
static int searchRecursive(int[] arr, int target, int index) {
if (index == arr.length) {
return -1; // base case: nothing left
}
if (arr[index] == target) {
return index; // base case: found
}
return searchRecursive(arr, target, index + 1);
}
public static void main(String[] args) {
int[] marks = {72, 85, 64, 85, 90, 85, 58};
System.out.println("Marks: [72, 85, 64, 85, 90, 85, 58]");
System.out.println("First 85 at index: " + firstIndex(marks, 85));
System.out.println("Last 85 at index: " + lastIndex(marks, 85));
System.out.println("85 appears " + countOccurrences(marks, 85) + " times");
System.out.println("All indexes of 85: " + allIndexes(marks, 85));
System.out.println("Recursive search for 90: " + searchRecursive(marks, 90, 0));
System.out.println("Recursive search for 100: " + searchRecursive(marks, 100, 0));
String[] names = {"Aarav", "Diya", "Kabir", "Meera"};
System.out.println("Kabir found at index: " + searchName(names, "Kabir"));
System.out.println("Rohan found at index: " + searchName(names, "Rohan"));
}
}Output:
Marks: [72, 85, 64, 85, 90, 85, 58]
First 85 at index: 1
Last 85 at index: 5
85 appears 3 times
All indexes of 85: [1, 3, 5]
Recursive search for 90: 4
Recursive search for 100: -1
Kabir found at index: 2
Rohan found at index: -1Linear Search in Java's Built-in Methods
You have probably already used linear search without realising it. Many Java methods scan elements one by one internally:
Method | What it does | Time |
|---|---|---|
| First index of a character | O(n) |
| First index of an element | O(n) |
| Calls | O(n) |
| Walks node by node | O(n) |
So when you write list.contains(x) inside a loop that runs n times, you are actually writing an O(n²) algorithm. This is a very common hidden performance problem in interview solutions.
Common Mistakes
1. Returning -1 Too Early
This is the most common bug beginners write:
// WRONG
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
} else {
return -1; // gives up after checking only arr[0]
}
}
return -1;
}If the first element is not the target, this method immediately returns -1 without checking the rest. The "not found" answer must come after the loop finishes.
2. Using == for Strings
names[i] == target // compares references (may be false even if text is same)
names[i].equals(target) // compares the actual text (correct)3. Off-by-One Loop Bounds
Writing i <= arr.length instead of i < arr.length will try to read arr[arr.length] and throw an ArrayIndexOutOfBoundsException.
4. Stopping When You Should Not
For "count" or "find all" problems, you must scan the full array. Putting a return or break on the first match gives a wrong answer.
When Should You Use Linear Search?
Linear search is the right choice when:
The data is unsorted and you search only once or a few times
The collection is small (for a few dozen elements, linear search is often as fast as anything else)
The data structure does not allow random access, such as a linked list
You need to check a condition rather than an exact value, for example "the first student who scored below 40"
It is the wrong choice when:
The data is large and already sorted — binary search is much faster
You need to search the same data many times — it is usually better to sort it once, or store it in a hash-based structure
Here is a quick preview of the difference, which we will explore in the next chapter:
Number of elements | Linear search (worst case) | Binary search (worst case) |
|---|---|---|
1,000 | 1,000 comparisons | about 10 comparisons |
1,000,000 | 1,000,000 comparisons | about 20 comparisons |
But remember: binary search only works on sorted data. Linear search works on anything.
Interview Tips and Practice Problems
Linear search is rarely asked directly, but it is the starting point of many problems. Interviewers often expect you to first describe the simple O(n) scan and then improve it.
Try these problems using a single pass:
Find the largest and smallest element in an array
Find the second largest element in one pass
Check whether an array contains any negative number
Find the first non-repeating character in a string (hint: count first, then search)
Find the index of the first element greater than a given value
Search for a target in a 2D matrix (row by row, like in the 2D Arrays chapter)
A useful habit: whenever your solution has a linear search inside another loop, ask yourself, "Can I avoid repeating this scan?" That question leads to better algorithms.
The Main Idea
Linear Search checks elements one by one until it finds the target or reaches the end.
Start
↓
Compare current element with target
↓
Equal? → Yes → return index
↓ No
Move to next element
↓
End of array? → return -1The facts to remember:
Best case → O(1)
Average case → O(n)
Worst case → O(n)
Space → O(1)
Sorted data needed? → NoLinear search is simple, works on any data in any order, and costs O(n) time. When the data is sorted, a much faster approach exists — and that is exactly what we will learn next with Binary Search.