Linear Search
Last updated
Linear search (also called sequential search) is the simplest search algorithm: start at the first element and compare each one with the target until you find a match or run out of elements. It makes no assumptions about the data — the array can be unsorted, and the elements can be anything you can compare for equality.
The animation above highlights each comparison as the scan moves left to right and stops the moment the target appears. Its simplicity costs speed: in the worst case every element is checked, so it runs in O(n). When the data is sorted, binary search finds the same answer in O(log n) — and if you need sorted data first, see merge sort.
Time & space complexity
| Case | Complexity | Notes |
|---|---|---|
| Best case | O(1) | The first element is the target. |
| Average case | O(n) | On average half the elements are checked before a hit. |
| Worst case | O(n) | The target is last — or not present at all. |
| Space | O(1) | Only the current index is kept. |
Step by step
| Step | What happens |
|---|---|
| 1 | Start at index 0, the first element of the array. |
| 2 | Compare the current element with the target value. |
| 3 | If they are equal, return the current index — found. |
| 4 | Otherwise move one position to the right and repeat. |
| 5 | If the end of the array is reached without a match, the target is not present (return -1). |
Worked example
Searching for 5 in [7, 3, 9, 1, 5, 8, 2]:
| Comparison | Index | Element | Result |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5 — keep scanning. |
| 2 | 1 | 3 | 3 ≠ 5 — keep scanning. |
| 3 | 2 | 9 | 9 ≠ 5 — keep scanning. |
| 4 | 3 | 1 | 1 ≠ 5 — keep scanning. |
| 5 | 4 | 5 | 5 = 5 — found at index 4. |
When to use linear search
| Use it when | Avoid it when |
|---|---|
| The data is unsorted or constantly changing | The data is sorted — binary search is exponentially faster |
| The collection is small, so simplicity wins | The dataset is large and searched repeatedly |
| You only have sequential access (streams, linked lists) | You can afford an index or hash table for O(1) lookups |
Linear Search code
A clean, runnable Linear Search implementation in Python, JavaScript, Java, C++, C, Pseudocode. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Linear Search code in Python
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Linear Search code in JavaScript
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Linear Search code in Java
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Linear Search code in C++
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Linear Search code in C
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Linear Search code in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)Linear Search FAQ
What is the time complexity of linear search?
O(n) in the average and worst case — the scan may have to visit every element — and O(1) in the best case when the first element is the target. It uses O(1) extra space.Does linear search need sorted data?
No — that's its main advantage. Linear search works on completely unsorted data because it checks every element for equality; order never matters. Binary search, by contrast, only works on sorted arrays.
When is linear search better than binary search?
When the data is unsorted and searched only once (sorting first would cost
O(n log n)), when the collection is tiny, or when you only have sequential access such as a stream or a linked list. For repeated lookups on sorted arrays, binary search wins.Is linear search the same as sequential search?
Yes — the two names describe the same algorithm: scan the elements in sequence until the target is found or the collection ends.
How many comparisons does linear search make on average?
If the target is present and equally likely to be anywhere, about
n/2 comparisons on average; if the target is absent, exactly n. That linear growth is why it's called linear search.Related resources
More visualizations
