Register for 45 Day Coding Challenge by CodeStudio And Win Some Exciting Prizes

# Linear Search

Linear search or Sequential search in data structure | The Linear search or Sequential search is a method to finding an element within a given list or array. Linear search or Sequential search is usually very simple to implement and is practical when the list has only a few elements, or when performing a single search in an unordered list.

Example:-
Array = {50, 90, 30, 70, 60};

Input to Search = 30
Output:- 30 found at Index 2.

Input to Search = 10

## How Linear Search in Works?

In Linear search, finds the index or location of search in the given array. It begins the search by comparing the search key and the first element of the array/list. If the first element is not equal to the search key then it will compare with the next element, and so on until the match is found or the end of the array. If the match is found then it returns its index, else it will reach the end of the array or list which means the search key is not available.

Let us understand it through an example:- Given array = {50, 90, 30, 70, 60};

Assume the search key = 30; Then traverse through the array and compare with each element. The first element of the array is 50, but 50 is not equal to 30 therefore move to the next element. The next element is 90, but it is also not equal to 30 therefore move to the next element. The next element of the array is 30 which is equal to the search key 30 therefore return the index of the current element of the array.

It was the situation where the search key exists in the array, now let us assume when the search key is not available. Assume the search key = 10. Traverse through the array and compare with each element. It won’t match with 50, 90, 30, 70, 60, and finally reached the end of the array. Therefore return -1 which means the search key is not available.

## Linear Search Algorithm

The procedure to find an element in a given array or list through linear search,
a) Take array, size of the array, and the search key. Assume they are:- array, n, and key
b) Traverse through the array.
c) Compare key with each element.
d) If the match is found then return the position.
e) Else repeat the process until the end of the array.
f) After traversing the array If the match is not found then return -1.

The algorithm for linear or sequential search can be given as,

``````linear search(array, n, key) {
i = 0;
while(i < n) {
if(key == array[i])
then return i;
else
i= i + 1;
}
return -1;
}``````

The time complexity of the above algorithm:- O(n)

• Best-case performance:- O(1). When the search key is present at the first index/position of the array then only one comparison is required.
• Worst-case performance:- O(n). When the search key is present at the last index of the array then it requires an N comparison, where N is the size of the array.

## Program

Let us demonstrate a linear search program in the C programming language using function.

``````#include <stdio.h>
// function for linear search
/* if match found then return index of search key
else return -1 */
int linearSearch(int arr[], int n, int key)
{
for(int i=0; i<n; i++)
{
if(key == arr[i])
return i;
}
return -1;
}

// main function
int main()
{
int array[] = {50, 90, 30, 70, 60};
int key = 0;

printf("Enter Search Element: ");
scanf("%d", &key);

// find the size array
int size = sizeof(array)/sizeof(array);

// search key
int index = linearSearch(array, size, key);

if(index == -1)
else
printf("%d Found at Index = %d\n", key, index);

return 0;
}``````

Output:-

Enter Search Element: 30
30 Found at Index = 2

Enter Search Element: 10

Enter Search Element: 60
60 Found at Index = 4

Let us demonstrate a linear search program in the C++ programming language.

``````#include<iostream>
using namespace std;
// function for linear search
/* if match found then return index of search key
else return -1 */
int linearSearch(int arr[], int n, int key)
{
for(int i=0; i<n; i++)
{
if(key == arr[i])
return i;
}
return -1;
}
// main function
int main()
{
int array[] = {50, 90, 30, 70, 60};
int key = 70;

// find the size array
int size = sizeof(array)/sizeof(array);

// search key
int index = linearSearch(array, size, key);

if(index == -1)
else
cout << key << " Found at Index = " << index << endl;

return 0;
}``````

Output:-

70 Found at Index = 3

Let us see the linear search program in the Java programming language.

``````public class Search {
public static void main(String[] args) {

int arr[] = { 50, 90, 30, 70, 60 }; // array
int key = 70; // search key
int size = arr.length; // size of array

// linear search
int index = linearSearch(arr, size, key);

// display result
if (index == -1)
else
System.out.println(key + " Found at Index = " + index);

}

// Method for linear search
/* If match found then return index of search key
* else return -1 */
public static int linearSearch(int[] arr, int size, int key) {
// traverse through the array
for (int i = 0; i < size; i++) {
if (key == arr[i])
return i;
}
return -1;
}

}``````

Output:-

70 Found at Index = 3

Let us see the program in Python.

``````# Python program for linear search

def linearSearch(arr, key):  #user-defined function
for i in range(len(arr)):
if (arr[i] == key):
return i
return -1

arr = [50, 90, 30, 70, 60]  #array
key = 70  #search key

index = linearSearch(arr, key) #calling function

# display result
if (index == -1):
else:
print(key, 'Found at Index', index)``````

Output:-

70 Found at Index 3

Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster-searching comparison to Linear search.

The main disadvantages of linear search are:-

• It needs more space and time complexity.
• If the key element is the last element and the search is from the first element then it is a worst-case. Similar if the key is at the first element and the search is from the last element then again it is a worst-case.

## Improved Version

We get worst-case performance O(n) because we are comparing array elements only from one side. Instead of one side, if we compare the array elements from both ends i.e. from the front and last then it will reduce the number of iterations. Let us understand it through an example,

Array = {10, 20, 30, 40, 50};
Search key = 40;
In the first iteration, 40 is not equal to 10 (from the left side), and 40 is not equal to 50 (from the right side).
In the second iteration, 40 is not equal to 20 (from the left side), but 40 is equal to 40.
Therefore the search key is found at index 3.

The normal approach can find it in 4 iterations, but an improved linear search can find it in only 2 iterations.

The algorithm for improved Linear Search can be written as,

``````linear search(array, n, key) {
i = 0;
j = n - 1;
while(i <= n/2) {
if(key == array[i])
then return i;
else if(key == array[j])
then return j;
else
i = i + 1;
j = j - 1;
}
return -1;
}``````

The best-case time complexity is the same as the previous:- O(1)
The worst-case time complexity:- O(n/2)

C Program for the above improved linear search,

``````#include <stdio.h>
// function for linear search
/* if match found then return index of search key
else return -1 */
int linearSearch(int arr[], int n, int key)
{
for(int i=0, j=n-1; i<=n/2; i++, j--)
{
if(key == arr[i])
return i;
if(key == arr[j])
return j;
}
return -1;
}

// main function
int main()
{
int array[] = {50, 90, 30, 70, 60};
int key = 0;

printf("Enter Search Element: ");
scanf("%d", &key);

// find the size array
int size = sizeof(array)/sizeof(array);

// search key
int index = linearSearch(array, size, key);

if(index == -1)
else
printf("%d Found at Index = %d\n", key, index);

return 0;
}``````

Output:-

Enter Search Element: 70
70 Found at Index = 3

Q) Which of the following is a disadvantage of linear search?
a) Requires more space
b) Greater time complexities compared to other searching algorithms
c) Not easy to understand
d) All of these

Ans:- b) Greater time complexities compared to other searching algorithms.

Also See:-

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!