In programming languages, we have 2 types of searching algorithms - Linear Search and Binary Search.
In this article, we will discuss Linear Search. Searching is a technique for finding any element in a list of elements. If the element is present in the list then the search is successful and it returns the location of the element where it is present. When a certain element is not found, the search is considered unsuccessful.
Linear search is a method for searching for a particular item in a collection of items. It is also known as sequential search or sequential search. It is the most straightforward search algorithm.
Linear search works by comparing each item in the collection one at a time with the item being searched for, until a match is found or until all the items have been searched. The key idea behind linear search is to sequentially check each element of the collection until the desired element is found.
An example of linear search is looking up a phone number in a phone book. In this situation, the person would start at the beginning of the phone book and check each page until the desired phone number is found.
Linear search is useful for small collections of items, especially when the number of items is known because the search can be completed quickly. However, it is not an efficient algorithm for large collections of items because it requires examining each item in the collection.
There are many applications of linear search. For example, it can be used to check if a particular element is present in an array. It can also be used to find the position of an element in an array. Additionally, the linear search can be used to look up values in a database.
In conclusion, linear search is a useful search algorithm for small collections of items. It is simple to implement and requires examining each item in the collection, which makes it suitable for small collections of items. However, it is not an efficient algorithm for larger collections of items.
It is widely used to search for an element from an unordered list, i.e., one in which items are not sorted. Linear search's worst-case time complexity is O(n). As an example, if we have a list of 10 items, and the element to be found is at the last index, a linear search will require 10 steps to find the item.
The following is the linear search algorithm that illustrates how it works.
How Linear Search Works?
Step 1:- First read the search(Target) element in the array.
Step 2:- Now compare the target element with the very first element in the array.
Step 3:- The linear search function will end if the target element matches the first element and displays a message stating "Target element found."
Step 4:- If both are not matched then compare the next element in the array.
Step 5:- Repeat step 3 & 4 until the "Target" element is compared with the last element of the array.
Step 6:- The Linear Search Function will be terminated if the last element in the list does not match, and the message "Element is not found" will appear.
Algorithm
Linear Search ( Array Arr, Value a ) // Arr is the name of the array, and a is the searched element.
Step 1: Set i=0 // i is the index of an array which starts from 0
Step 2: if i>n then go to step 7 // n is the number of elements in array
Step 3: if Arr[i] = a then go to step 6
Step 4: Set i=i+1
Step 5: Goto step 2
Step 6: Print element a found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
Pseudocode
Start
linear_search ( Array, value)
For each element in the array
If (searched element == value)
Returns the searched element location
end if
end for
end
Example of Linear Search
Consider an array of size 7 with elements 13, 9, 21, 15, 39, 19, and 27 that starts with 0 and ends with size minus one, 6.
Search element = 39
Step 1: The searched element 39 is compared to the first element of an array, which is 13.
The match is not found, you now move on to the next element and try to implement a comparison.
Step 2: Now, search element 39 is compared to the second element of an array, 9.
As both are not matching, you will continue the search.
Step 3: Now, search element 39 is compared with the third element, which is 21.
Again, both the elements are not matching, you move onto the next following element.
Step 4: Next, search element 39 is compared with the fourth element, which is 15.
As both are not matching, you move on to the next element.
Step 5: Next, search element 39 is compared with the fifth element 39.
A perfect match is found, you stop comparing any further elements and terminate the Linear Search Algorithm and display the element found at location 4.
Complexity
Time Complexity
| Best Case | O(1) |
| Average Case | O(n) |
| Worst Case | O(n) |
Space Complexity:- O(1)
Implementation of Linear Search
Program for Linear Search in C:-
#include <stdio.h>
int linearSearch(int a[], int n, int val) {
// Going through array sequencially
for (int i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1;
}
int main() {
int a[] = {70, 40, 30, 11, 57, 41, 25, 14, 52}; // given array
int val = 41; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = linearSearch(a, n, val); // Store result
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", val);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
}
Output:-
Program for Linear Search in C++:-
#include <iostream>
using namespace std;
int linearSearch(int a[], int n, int val) {
// Going through array linearly
for (int i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1;
}
int main() {
int a[] = {69, 39, 29, 10, 56, 40, 24, 13, 51}; // given array
int val = 56; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = linearSearch(a, n, val); // Store result
cout<<"The elements of the array are - ";
for (int i = 0; i < n; i++)
cout<<a[i]<<" ";
cout<<"\nElement to be searched is - "<<val;
if (res == -1)
cout<<"\nElement is not present in the array";
else
cout<<"\nElement is present at "<<res<<" position of array";
return 0;
}
Output:-
Program for Linear Search in C#:-
using System;
class LinearSearch {
static int linearSearch(int[] a, int n, int val) {
// Going through array sequencially
for (int i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1;
}
static void Main() {
int[] a = {56, 30, 20, 41, 67, 31, 22, 14, 52}; // given array
int val = 14; // value to be searched
int n = a.Length; // size of array
int res = linearSearch(a, n, val); // Store result
Console.Write("The elements of the array are - ");
for (int i = 0; i < n; i++)
Console.Write(" " + a[i]);
Console.WriteLine();
Console.WriteLine("Element to be searched is - " + val);
if (res == -1)
Console.WriteLine("Element is not present in the array");
else
Console.Write("Element is present at " + res +" position of array");
}
}
Output:-
Program for Linear Search in Java:-
class LinearSearch {
static int linearSearch(int a[], int n, int val) {
// Going through array sequencially
for (int i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1;
}
public static void main(String args[]) {
int a[] = {55, 29, 10, 40, 57, 41, 20, 24, 45}; // given array
int val = 10; // value to be searched
int n = a.length; // size of array
int res = linearSearch(a, n, val); // Store result
System.out.println();
System.out.print("The elements of the array are - ");
for (int i = 0; i < n; i++)
System.out.print(" " + a[i]);
System.out.println();
System.out.println("Element to be searched is - " + val);
if (res == -1)
System.out.println("Element is not present in the array");
else
System.out.println("Element is present at " + res +" position of array");
}
}
Output:-
Program for Linear Search in JavaScript:-
<html>
<head>
</head>
<body>
<script>
var a = [54, 26, 9, 80, 47, 71, 10, 24, 45]; // given array
var val = 71; // value to be searched
var n = a.length; // size of array
function linearSearch(a, n, val) {
// Going through array sequencially
for (var i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1
}
var res = linearSearch(a, n, val); // Store result
document.write("The elements of the array are: ");
for (i = 0; i < n; i++)
document.write(" " + a[i]);
document.write("<br>" + "Element to be searched is: " + val);
if (res == -1)
document.write("<br>" + "Element is not present in the array");
else
document.write("<br>" + "Element is present at " + res +" position of array");
</script>
</body>
</html>
Output:-
Program for Linear Search in PHP:-
<?php
$a = array(45, 24, 8, 80, 62, 71, 10, 23, 43); // given array
$val = 62; // value to be searched
$n = sizeof($a); //size of array
function linearSearch($a, $n, $val) {
// Going through array sequencially
for ($i = 0; $i < $n; $i++)
{
if ($a[$i] == $val)
return $i+1;
}
return -1;
}
$res = linearSearch($a, $n, $val); // Store result
echo "The elements of the array are: ";
for ($i = 0; $i < $n; $i++)
echo " " , $a[$i];
echo "<br>" , "Element to be searched is: " , $val;
if ($res == -1)
echo "<br>" , "Element is not present in the array";
else
echo "<br>" , "Element is present at " , $res , " position of array";
?>
Output:-
Program for Linear Search in Python:-
# Linear Search in Python
def linearSearch(array, n, x):
# Going through array sequencially
for i in range(0, n):
if (array[i] == x):
return i
return -1
array = [2, 4, 0, 1, 9]
x = 1
n = len(array)
result = linearSearch(array, n, x)
if(result == -1):
print("Element not found")
else:
print("Element found at index: ", result)
Output:-
Applications of Linear Search
Linear search can be applied to both single-dimensional and multi-dimensional arrays.
Linear search is easy to implement and effective when the array contains only a few elements.
Linear Search is also efficient when the search is performed to fetch a single search in an unordered - List.