Linear Search
What Is Linear Search?
Linear search is the simplest searching algorithm. It examines every element in a collection one by one, from start to end, until the target is found or the collection is exhausted.
Array: [5, 3, 8, 1, 9, 2, 7] Target: 9 Step 1: arr[0]=5 ≠ 9 → continue Step 2: arr[1]=3 ≠ 9 → continue Step 3: arr[2]=8 ≠ 9 → continue Step 4: arr[3]=1 ≠ 9 → continue Step 5: arr[4]=9 = 9 → FOUND at index 4 ✓
No sorting required. No preprocessing. Works on any collection in any order. The trade-off: it examines every element up to the target — O(n) in the worst case.
Basic Linear Search
1public class LinearSearch {
2
3 // Returns the index of target, or -1 if not found
4 public static int linearSearch(int[] arr, int target) {
5 for (int i = 0; i < arr.length; i++) {
6 if (arr[i] == target) {
7 return i; // Found — return index immediately
8 }
9 }
10 return -1; // Not found
11 }
12
13 // Returns true/false (useful when index is not needed)
14 public static boolean contains(int[] arr, int target) {
15 for (int value : arr) {
16 if (value == target) return true;
17 }
18 return false;
19 }
20
21 // Find ALL occurrences — returns list of indices
22 public static java.util.List<Integer> findAll(int[] arr, int target) {
23 java.util.List<Integer> indices = new java.util.ArrayList<>();
24 for (int i = 0; i < arr.length; i++) {
25 if (arr[i] == target) indices.add(i);
26 }
27 return indices;
28 }
29
30 public static void main(String[] args) {
31 int[] arr = {5, 3, 8, 1, 9, 2, 7};
32
33 System.out.println(linearSearch(arr, 9)); // 4
34 System.out.println(linearSearch(arr, 6)); // -1
35 System.out.println(contains(arr, 3)); // true
36
37 int[] arr2 = {1, 3, 5, 3, 8, 3};
38 System.out.println(findAll(arr2, 3)); // [1, 3, 5]
39 }
40}Output:
4
-1
true
[1, 3, 5]
Dry Run: Basic Linear Search
arr = [5, 3, 8, 1, 9, 2, 7], target = 1 i=0: arr[0]=5 ≠ 1 → continue i=1: arr[1]=3 ≠ 1 → continue i=2: arr[2]=8 ≠ 1 → continue i=3: arr[3]=1 = 1 → return 3 ✓ Total comparisons: 4 Worst case — target = 7 (last element): i=0: 5≠7, i=1: 3≠7, i=2: 8≠7, i=3: 1≠7, i=4: 9≠7, i=5: 2≠7, i=6: 7=7 → return 6 Total comparisons: 7 = n Target not found (target = 4): Compare all 7 elements, none match → return -1 Total comparisons: 7 = n
Sentinel Linear Search
Standard linear search checks two conditions per iteration: the bounds check i < n and the value comparison arr[i] == target. The sentinel technique eliminates the bounds check by placing the target value at arr[n] before searching — guaranteeing the search loop will always terminate on a match.
Standard: while (i < n && arr[i] != target) → 2 comparisons per step Sentinel: arr[n] = target; while (arr[i] != target) → 1 comparison per step Why it works: If the target exists in arr[0..n-1]: found at its normal index. If the target does NOT exist: the sentinel at arr[n] is found — return -1. The bounds check i < n is never needed because the sentinel guarantees termination.
1public class SentinelSearch {
2
3 // Requires writable array with one extra slot (length = n+1)
4 public static int sentinelSearch(int[] arr, int n, int target) {
5 int last = arr[n - 1]; // Save last element
6 arr[n - 1] = target; // Place sentinel at last real position
7 // (or arr[n] if array has n+1 capacity)
8
9 int i = 0;
10 while (arr[i] != target) {
11 i++; // Only ONE comparison per step
12 }
13
14 arr[n - 1] = last; // Restore last element
15
16 // Check if found in actual array or only at sentinel
17 if (i < n - 1 || arr[n - 1] == target) {
18 return i;
19 }
20 return -1;
21 }
22
23 // Clean version: use a copy with an extra slot
24 public static int sentinelSearchClean(int[] arr, int target) {
25 int n = arr.length;
26 int[] extended = java.util.Arrays.copyOf(arr, n + 1);
27 extended[n] = target; // Sentinel at index n
28
29 int i = 0;
30 while (extended[i] != target) i++;
31
32 return i < n ? i : -1; // Found in real array or only at sentinel?
33 }
34
35 public static void main(String[] args) {
36 int[] arr = {5, 3, 8, 1, 9, 2, 7};
37
38 System.out.println(sentinelSearchClean(arr, 9)); // 4
39 System.out.println(sentinelSearchClean(arr, 6)); // -1
40 System.out.println(sentinelSearchClean(arr, 5)); // 0
41 }
42}Output:
4
-1
0
Dry Run: Sentinel Search — target = 6 (not in array)
arr = [5, 3, 8, 1, 9, 2, 7], target = 6
After sentinel: [5, 3, 8, 1, 9, 2, 7, 6]
0 1 2 3 4 5 6 7(sentinel at n=7)
Loop (only ONE comparison per step):
i=0: arr[0]=5 ≠ 6 → i++
i=1: arr[1]=3 ≠ 6 → i++
i=2: arr[2]=8 ≠ 6 → i++
i=3: arr[3]=1 ≠ 6 → i++
i=4: arr[4]=9 ≠ 6 → i++
i=5: arr[5]=2 ≠ 6 → i++
i=6: arr[6]=7 ≠ 6 → i++
i=7: arr[7]=6 = 6 → STOP
i=7 = n → not in real array → return -1
Standard search would have done: (i<n && arr[i]!=6) — 2 conditions × 8 steps = 16 checks
Sentinel search: (arr[i]!=6) — 1 condition × 8 steps = 8 checks
Linear Search on Sorted Arrays — Early Termination
When the array is sorted, linear search can terminate early: as soon as an element greater than the target is found, the target cannot exist further in the array.
1public class SortedLinearSearch {
2
3 // Linear search on sorted array with early termination — O(n) worst, better average
4 public static int searchSorted(int[] arr, int target) {
5 for (int i = 0; i < arr.length; i++) {
6 if (arr[i] == target) return i;
7 if (arr[i] > target) return -1; // Early exit — target can't be here
8 }
9 return -1;
10 }
11
12 public static void main(String[] args) {
13 int[] sorted = {1, 3, 5, 7, 9, 11, 13};
14
15 System.out.println(searchSorted(sorted, 7)); // 3
16 System.out.println(searchSorted(sorted, 6)); // -1 (stops at 7, not 13)
17 System.out.println(searchSorted(sorted, 15)); // -1 (reaches end)
18 }
19}Output:
3
-1
-1
Linear Search in 2D Arrays
Extend linear search to a matrix by scanning row by row, or with early termination if the matrix is sorted.
1public class LinearSearch2D {
2
3 // Unsorted matrix — scan every element
4 public static int[] searchMatrix(int[][] matrix, int target) {
5 for (int r = 0; r < matrix.length; r++) {
6 for (int c = 0; c < matrix[r].length; c++) {
7 if (matrix[r][c] == target) return new int[]{r, c};
8 }
9 }
10 return new int[]{-1, -1}; // Not found
11 }
12
13 // Row-sorted matrix — use early termination within each row
14 public static int[] searchRowSorted(int[][] matrix, int target) {
15 for (int r = 0; r < matrix.length; r++) {
16 for (int c = 0; c < matrix[r].length; c++) {
17 if (matrix[r][c] == target) return new int[]{r, c};
18 if (matrix[r][c] > target) break; // Target can't be in this row
19 }
20 }
21 return new int[]{-1, -1};
22 }
23
24 public static void main(String[] args) {
25 int[][] mat = {
26 {1, 3, 5},
27 {7, 9, 11},
28 {13, 15, 17}
29 };
30
31 int[] res = searchMatrix(mat, 9);
32 System.out.println("[" + res[0] + ", " + res[1] + "]"); // [1, 1]
33
34 res = searchMatrix(mat, 6);
35 System.out.println("[" + res[0] + ", " + res[1] + "]"); // [-1, -1]
36 }
37}Output:
[1, 1]
[-1, -1]
Linear Search on Strings and Objects
Linear search generalises to any type that supports equality comparison.
1import java.util.*;
2
3public class LinearSearchGeneric {
4
5 // Search in a list of strings
6 public static int searchString(String[] arr, String target) {
7 for (int i = 0; i < arr.length; i++) {
8 if (arr[i].equals(target)) return i; // Use .equals(), not ==
9 }
10 return -1;
11 }
12
13 // Find element satisfying a condition (predicate)
14 public static <T> int findFirst(T[] arr, java.util.function.Predicate<T> condition) {
15 for (int i = 0; i < arr.length; i++) {
16 if (condition.test(arr[i])) return i;
17 }
18 return -1;
19 }
20
21 public static void main(String[] args) {
22 String[] names = {"Alice", "Bob", "Charlie", "Diana"};
23 System.out.println(searchString(names, "Charlie")); // 2
24 System.out.println(searchString(names, "Eve")); // -1
25
26 Integer[] nums = {3, 7, 1, 9, 4};
27 // Find first element > 5
28 System.out.println(findFirst(nums, x -> x > 5)); // 1 (arr[1]=7)
29 // Find first even number
30 System.out.println(findFirst(nums, x -> x % 2 == 0)); // 4 (arr[4]=4)
31 }
32}Output:
2
-1
1
4
When to Use Linear Search
Use linear search when: ✓ The array is unsorted and cannot be sorted ✓ The array is very small (n < ~20) — overhead of binary search setup exceeds benefit ✓ You need to find ALL occurrences, not just one ✓ The elements are not comparable by order (only equality) ✓ You are searching a linked list (no random access) ✓ The array changes frequently (maintaining a sorted structure is expensive) ✓ You need the first element satisfying a complex condition (predicate) Use binary search instead when: ✗ The array is sorted and n is large (binary search is O(log n)) ✗ You need the insertion point, lower bound, or upper bound ✗ Multiple searches on the same sorted array (amortise sort cost) Linear search is always correct. Binary search is faster but requires sorted input. When in doubt about sortedness — use linear search.
Complexity Summary
| Variant | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Basic linear search | O(1) — found at index 0 | O(n/2) ≈ O(n) | O(n) | O(1) |
| Sentinel linear search | O(1) | O(n) — fewer comparisons per step | O(n) | O(1) |
| Sorted early-termination | O(1) | O(n/2) | O(n) | O(1) |
| 2D matrix (r×c) | O(1) | O(r×c/2) | O(r×c) | O(1) |
Why O(n) average with O(n/2) steps? If the target is equally likely to be at any position, its expected position is n/2. But O(n/2) = O(n) under asymptotic notation — the constant is dropped.
Common Mistakes
Using == instead of .equals() for string/object comparison in Java. == compares references, not values. "hello" == "hello" may be false for strings not from the string pool. Always use .equals() for object equality in Java. In Python, == compares values correctly for all built-in types.
Forgetting to restore the original array after sentinel search. The sentinel modifies the array (appends or overwrites an element). If the original array is needed after the search, always remove or restore the sentinel before returning. The Python implementation above demonstrates arr.pop() before the return statement.
Not returning -1 when the target is absent. Returning 0 by default (the common mistake) gives a false positive for targets at index 0 versus targets that are absent — both return the same value. Always initialise the result to -1 and only change it on a successful match.
Modifying the loop variable inside the loop. In languages like C++ and Java, manually incrementing i inside a for-loop that already increments i in the update clause skips elements. The sentinel search loop uses a while loop to avoid this.
Interview Questions
Q: What is the time complexity of linear search and why?
O(n) worst case. In the worst case, the target is at the last index or absent — every element must be compared once. With n elements, that is n comparisons = O(n). Average case is O(n/2) comparisons, which is still O(n) asymptotically. Best case is O(1) — the target is at the first index.
Q: When would you choose linear search over binary search even on a sorted array?
For very small arrays (n < ~10-20), the constant-factor overhead of binary search's index arithmetic may not be worth it. For single-element arrays, linear search returns immediately. If the sorted array is linked-list-backed (no random index access), binary search cannot be applied at all — linear search is the only option.
Q: What is the sentinel optimisation and how many comparisons does it save?
Standard linear search does two comparisons per iteration: bounds check (i < n) and value check (arr[i] == target). The sentinel eliminates the bounds check by placing the target at the end of the array — the loop always terminates on a value match, never on bounds. For a scan of n elements, this saves n bounds checks — halving the total number of comparisons from 2n to n.
FAQs
Is the in operator in Python a linear search?
Yes. x in list performs a linear scan — O(n) in the worst case. It is equivalent to calling any(item == x for item in list). For O(1) membership testing, use a set or dict. The in operator on a set is O(1) average, not O(n).
Does linear search work on linked lists?
Yes — and it is the only option for linked lists without random access. Traverse from the head node, comparing each node's value. This is the same O(n) time but cannot use the sentinel technique (cannot append to a linked list in O(1) without a tail pointer). Binary search on linked lists would require O(n) to reach the midpoint — worse than linear search.
Why is the sentinel technique not commonly used in production code?
Modern branch predictors and out-of-order execution in CPUs often make the two-condition check nearly as fast as the one-condition sentinel check. The sentinel requires modifying the array or allocating extra space, which adds complexity. For small arrays, the overhead of the sentinel setup exceeds the savings. For large arrays where performance matters, binary search (O(log n)) is preferred anyway.
Summary
Linear search is the foundation of all searching algorithms — simple, universal, and requiring no preprocessing.
The three key variants:
- ›Basic linear search — scan left to right, return index on match, -1 on exhaustion — O(n) time, O(1) space
- ›Sentinel linear search — place target at arr[n] to eliminate bounds check — same O(n) but half the comparisons per step
- ›Sorted early-termination — stop as soon as an element exceeds the target — same worst case, better average
Core rules:
- ›Use
.equals()not==for object comparison in Java - ›Always restore the array after sentinel search
- ›Return -1 (not 0 or null) to signal "not found"
- ›For strings:
==works in Python/JS/C++; use.equals()only in Java
In the next topic, you will explore Binary Search — the O(log n) alternative that cuts the search space in half at every step, requiring a sorted input.
What is the worst-case time complexity of linear search on an array of n elements?