Course Content
Introduction to Data Structure
0/1
Sorting Algorithms
0/9
Searching Algorithms
0/3
Data Structures and Algorithms
About Lesson

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

CaseTime Complexity
Best CaseO(1)
Average CaseO(n)
Worst CaseO(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.