Linear search (also called sequential search) is the simplest and most straightforward searching algorithm. It works by checking each element of the array sequentially from the beginning to the end until the target element is found or the entire array has been traversed. Unlike binary search, linear search doesn't require the array to be sorted, making it versatile for any type of data structure.
The algorithm starts at the first element (index 0) and compares it with the target value. If they match, the search is successful and the index is returned. If not, it moves to the next element and repeats the process. This continues until either the target is found or all elements have been checked.
Consider searching for the number 7 in the array: [5, 3, 8, 1, 9, 2, 7, 4, 6]
Where n is the number of elements in the array. In the worst case, we need to check all n elements, making it a linear time algorithm.
| Case | Time Complexity | When It Occurs | Example |
|---|---|---|---|
| Best Case | O(1) | Target is the first element | Search 5 in [5, 3, 8, 1] |
| Average Case | O(n/2) ~= O(n) | Target is in the middle | Search 8 in [5, 3, 8, 1, 9] |
| Worst Case | O(n) | Target is last or not present | Search 9 in [5, 3, 8, 1, 9] |
| Space Complexity | O(1) | No extra memory needed | Only uses a few variables |
public class LinearSearch {
// Iterative linear search - O(n) time, O(1) space
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Found at index i
}
}
return -1; // Not found
}
// Recursive linear search - O(n) time, O(n) space (call stack)
static int linearSearchRec(int[] arr, int index, int target) {
// Base case 1: Reached end of array
if (index == arr.length) {
return -1; // Not found
}
// Base case 2: Found the target
if (arr[index] == target) {
return index;
}
// Recursive case: Search in remaining array
return linearSearchRec(arr, index + 1, target);
}
// Find ALL occurrences of target
static void findAllOccurrences(int[] arr, int target) {
boolean found = false;
System.out.print("Indices where " + target + " is found: ");
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
System.out.print(i + " ");
found = true;
}
}
if (!found) {
System.out.print("Not found");
}
System.out.println();
}
// Linear search with custom comparator (for objects)
static <T> int linearSearchGeneric(T[] arr, T target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i].equals(target)) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 1, 9, 2, 7, 4, 6};
// Test iterative search
System.out.println("Array: [5, 3, 8, 1, 9, 2, 7, 4, 6]");
System.out.println("Search 7: index " + linearSearch(arr, 7)); // 6
System.out.println("Search 10: index " + linearSearch(arr, 10)); // -1
// Test recursive search
System.out.println("Recursive search 9: index " +
linearSearchRec(arr, 0, 9)); // 4
// Test find all occurrences
int[] arr2 = {3, 1, 4, 1, 5, 9, 2, 6, 1};
System.out.println("\nArray: [3, 1, 4, 1, 5, 9, 2, 6, 1]");
findAllOccurrences(arr2, 1); // Indices: 1 3 8
// Test with strings
String[] names = {"Alice", "Bob", "Charlie", "David"};
System.out.println("\nSearch 'Charlie': index " +
linearSearchGeneric(names, "Charlie")); // 2
}
}
/*
* Trace for arr = {5, 3, 8, 1, 9}, target = 9:
*
* i=0: arr[0]=5 != 9 -> continue
* i=1: arr[1]=3 != 9 -> continue
* i=2: arr[2]=8 != 9 -> continue
* i=3: arr[3]=1 != 9 -> continue
* i=4: arr[4]=9 = 9 -> return 4 [ok]
*/# Linear Search in Python
def linear_search(arr, target):
"""Iterative linear search - O(n) time, O(1) space"""
for i in range(len(arr)):
if arr[i] == target:
return i # Found at index i
return -1 # Not found
def linear_search_recursive(arr, index, target):
"""Recursive linear search - O(n) time, O(n) space"""
# Base case 1: Reached end of array
if index == len(arr):
return -1
# Base case 2: Found the target
if arr[index] == target:
return index
# Recursive case
return linear_search_recursive(arr, index + 1, target)
def find_all_occurrences(arr, target):
"""Find all indices where target appears"""
indices = [i for i, val in enumerate(arr) if val == target]
return indices if indices else [-1]
# Test the functions
if __name__ == "__main__":
arr = [5, 3, 8, 1, 9, 2, 7, 4, 6]
print("Array:", arr)
print("Search 7:", linear_search(arr, 7)) # 6
print("Search 10:", linear_search(arr, 10)) # -1
print("Recursive search 9:", linear_search_recursive(arr, 0, 9)) # 4
arr2 = [3, 1, 4, 1, 5, 9, 2, 6, 1]
print("\nArray:", arr2)
print("All occurrences of 1:", find_all_occurrences(arr2, 1)) # [1, 3, 8]#include <stdio.h>
// Iterative linear search - O(n) time, O(1) space
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Found at index i
}
}
return -1; // Not found
}
// Recursive linear search - O(n) time, O(n) space
int linearSearchRec(int arr[], int index, int n, int target) {
// Base case 1: Reached end of array
if (index == n) {
return -1;
}
// Base case 2: Found the target
if (arr[index] == target) {
return index;
}
// Recursive case
return linearSearchRec(arr, index + 1, n, target);
}
int main() {
int arr[] = {5, 3, 8, 1, 9, 2, 7, 4, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array: [5, 3, 8, 1, 9, 2, 7, 4, 6]\n");
printf("Search 7: index %d\n", linearSearch(arr, n, 7)); // 6
printf("Search 10: index %d\n", linearSearch(arr, n, 10)); // -1
printf("Recursive search 9: index %d\n",
linearSearchRec(arr, 0, n, 9)); // 4
return 0;
}| Step | Action | Description |
|---|---|---|
| 1 | Start from index 0 | Begin at the first element of the array |
| 2 | Compare current element with target | Check if arr[i] == target |
| 3 | If match found | Return the current index i |
| 4 | If no match | Move to next element (i++) |
| 5 | Repeat steps 2-4 | Continue until target found or array ends |
| 6 | If array exhausted | Return -1 (not found) |
| Use Linear Search When | Use Binary Search When |
|---|---|
| Array is unsorted | Array is sorted |
| Array size is small (< 100 elements) | Array size is large (> 1000 elements) |
| Data structure is a linked list | Data structure is an array |
| Searching is infrequent | Searching is frequent |
| Simplicity is more important than speed | Performance is critical |
| Data changes frequently (no time to sort) | Data is static or rarely changes |
| Feature | Linear Search | Binary Search |
|---|---|---|
| Array requirement | Unsorted or sorted | Must be sorted |
| Time complexity (Best) | O(1) | O(1) |
| Time complexity (Average) | O(n) | O(log n) |
| Time complexity (Worst) | O(n) | O(log n) |
| Space complexity | O(1) | O(1) iterative, O(log n) recursive |
| Implementation | Very simple | More complex |
| Best for | Small or unsorted data | Large sorted data |
| Data structure | Arrays, linked lists | Arrays only |
| Example (n=1000) | ~500 comparisons (average) | ~10 comparisons (average) |
For an array of size n = 1,000,000:
This shows why binary search is dramatically faster for large sorted datasets. However, if the array is unsorted, sorting it first takes O(n log n) time, which might make linear search more efficient for a single search operation.
Explore 500+ free tutorials across 20+ languages and frameworks.