Linear Search Agorithm
Linear Search (also called sequential search) is a simple searching algorithm that checks each element in a list one by one until it finds the target element or reaches the end of the list.
It works on both sorted and unsorted arrays.
How Linear Search Works (Step-by-Step)
- Start from the first element of the array.
- Compare each element with the target/key you are looking for.
- If a match is found, return the index.
- If no match is found by the end, return -1 (or say “not found”).
Example
Array: [12, 45, 67, 23, 89] Target: 23
Step-by-Step Execution:
| Step | Element Checked | Is it equal to 23? | Result |
| 1 | 12 | No | Continue |
| 2 | 45 | No | Continue |
| 3 | 67 | No | Continue |
| 4 | 23 | Yes | Found at index 3 |
Linear Search code:
PythonJavaCC++
# Linear Search
def linearSearch(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
arr = [10, 20, 30, 40]
print(linearSearch(arr, 30)) # Output: 2
public class LinearSearch {
static int linearSearch(int arr[], int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target)
return i;
}
return -1;
}
public static void main(String[] args) {
int arr[] = {10,20,30,40};
System.out.println(linearSearch(arr,30)); // 2
}
}
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target)
return i;
}
return -1;
}
int main() {
int arr[] = {10,20,30,40};
int index = linearSearch(arr,4,30);
printf("%d\n", index);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int linearSearch(vector<int> arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target)
return i;
}
return -1;
}
int main() {
vector<int> arr = {10,20,30,40};
cout << linearSearch(arr,30); // 2
return 0;
}
Time Complexity
| Case | Time Complexity |
| Best Case | O(1) |
| Average | O(n) |
| Worst Case | O(n) |
- n = number of elements
Space Complexity
- O (1) — no extra space used
Key Features:
- Simple and easy
- Works for unsorted arrays
- Not efficient for large data sets