Linear Search or Sequential Search
Sequential search is also known as Linear Search.
In Sequential search, elements are examined sequentially starting from the first element. It examines all values in an array until it finds a match or reaches the end.
It is the simplest search algorithm. In linear search, each element of the list is matched with the item whose location is to be found, by traversing the list completely.
If the match is found, the algorithm returns the item's location; otherwise, it returns NULL.
Linear search has a worst-case time complexity of O(n).
Algorithm for searching an element key
in an array a[]
having n elements.
Simple Sequential Search
#include<stdio.h>
int sequential_search(int a[], int key, int n);
void main() {
int a[50], n, key, i;
printf("Enter no. of elements: ");
scanf("%d", &n);
printf("Enter %d numbers: ", n);
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Enter element to be search: ");
scanf("%d", &key);
i = sequential_search(a, key, n);
if(i != -1)
printf("Element found at location : %d", i);
else
printf("Element not found");
}
int sequential_search(int a[], int key, int n) {
int i = 0;
while(i < n && key != a[i])
i++;
if(i < n)
return i;
return -1;
}
public class Main {
public static void main(String[] args) {
int array [] = {3, 2, 4, 5, 3, 2, 7, 6, 4};
boolean number = sequentialSearch(array, 6);
if(number) {
System.out.println("Number found");
} else {
System.out.println("Number not found");
}
}
public static boolean sequentialSearch(int[] array, int b) {
for(int i : array) {
if(i == b)
return true;
}
return false;
}
}
Linear search has a time complexity O(n)
. Such algorithms are not suitable for searching when the number of elements is large.
Time Complexity
Case | Time Complexity |
---|---|
Best Case | O(1) |
Average Case | O(n) |
Worst Case | O(n) |
- Best Case O(1): It occurs when the element we are finding is at the first position of the array.
- Average Case O(n): Linear search has an average case time complexity of O(n)
- Worst Case O(n): The worst case scenario in linear search is when the target element doesn't exist in the given array, and we have to traverse the entire array.
The Linear search has a time complexity of O(n), because each element in the array is compared once.
Space Complexity
Linear search has a space complexity of O(1).