Linear Search from Scratch (2026)
Linear search (sequential search) is the simplest searching algorithm. It checks each element in a collection one by one until the target is found or the end is reached. With O(n) time complexity, it works on both sorted and unsorted arrays without any preprocessing. While not the fastest algorithm, it is the most versatile and requires no assumptions about the data.
In this tutorial, we will implement linear search with various optimizations including sentinel search, find all occurrences, find first and last occurrence, and search in 2D arrays. We will analyze when linear search is preferred over more efficient algorithms like binary search.
Basic Linear Search
Basic linear search iterates through the array from index 0 to n-1, comparing each element with the target. If found, it returns the index; otherwise, it returns -1. The best case is O(1) when the target is at the first position. The worst case is O(n) when the target is at the last position or not present. The average case is O(n/2) which simplifies to O(n).
Linear search is preferred when the array is small (n < 50), when the array is unsorted and will only be searched once, or when the data structure does not support random access (like linked lists).
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target: return i
return -1
def linear_search_all(arr, target):
return [i for i in range(len(arr)) if arr[i] == target]
def first_occurrence(arr, target):
for i in range(len(arr)):
if arr[i] == target: return i
return -1
def last_occurrence(arr, target):
result = -1
for i in range(len(arr)):
if arr[i] == target: result = i
return result
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
print(linear_search(arr, 5)) # 4
print(linear_search_all(arr, 1)) # [1, 3]Sentinel Linear Search
Sentinel search is an optimization that eliminates the need to check the array boundary (i < n) in each iteration. We place the target at the end of the array (the sentinel) and search until we find it. This reduces the number of comparisons per iteration from 2 to 1, providing a small but measurable speedup for large arrays.
The sentinel version performs n comparisons in the worst case instead of 2n, effectively halving the comparison count. This optimization was more significant when branch prediction was poor, but it still provides benefits in tight loops and performance-critical code.
#include
#include
using namespace std;
int sentinelSearch(vector& arr, int n, int target) {
int last = arr[n - 1];
arr[n - 1] = target;
int i = 0;
while (arr[i] != target) i++;
arr[n - 1] = last;
if (i < n - 1 || arr[n - 1] == target) return i;
return -1;
}
int main() {
vector arr = {3, 1, 4, 1, 5, 9, 2, 6};
int result = sentinelSearch(arr, arr.size(), 5);
cout << (result != -1 ? "Found at " + to_string(result) : "Not found") << endl;
} Linear Search on Sorted Arrays
When the array is sorted, we can optimize linear search by stopping early if we encounter an element greater than the target. This early termination reduces the average search time for elements that appear early in the array. However, in the worst case (target not present or at the end), the complexity remains O(n).
For sorted arrays, binary search with O(log n) is generally preferred. However, linear search can be faster for small arrays or when searching for elements near the beginning. Understanding both approaches helps in choosing the right algorithm for the specific use case.
public class LinearSearchSorted {
static int searchEarlyTermination(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
if (arr[i] > target) return -1;
}
return -1;
}
static int countOccurrences(int[] arr, int target) {
int count = 0;
for (int num : arr) {
if (num == target) count++;
if (num > target) break;
}
return count;
}
}Linear Search on 2D Arrays
Linear search extends naturally to 2D arrays by flattening the search space or using nested loops. We can search row by row or column by column. For sorted 2D arrays (each row and column is sorted), we can use more efficient algorithms, but basic linear search works for any 2D structure in O(m*n) time.
Common applications include finding elements in matrices, searching for patterns in images, and finding positions in game boards.
def search_2d(matrix, target):
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == target:
return (i, j)
return None
def search_sorted_matrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
for i in range(rows):
for j in range(cols):
if matrix[i][j] == target: return (i, j)
if matrix[i][j] > target: break
return None
matrix = [[1,4,7],[2,5,8],[3,6,9]]
print(search_2d(matrix, 5)) # (1, 1)Frequently Asked Questions
When to use linear search over binary search?
Use linear search when the array is unsorted, small (n < 50), searched only once, or when using linked lists. Binary search requires sorted arrays and O(1) random access.
What is sentinel search?
Sentinel search places the target at the end of the array to eliminate boundary checks in the loop. This reduces comparisons per iteration from 2 to 1, halving the total comparisons.
What is the time complexity of linear search?
Best case: O(1) when target is first element. Worst case: O(n) when target is last or not present. Average case: O(n) since on average you check n/2 elements.
Can linear search work on linked lists?
Yes, linear search is the standard search algorithm for linked lists since they don't support random access. The time complexity is O(n) in all cases.
Originally published on Ayodhyyya. Last updated June 1, 2026.