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.

 

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).

 

Example

C Program

#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;
}

 

Java Program

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.