1/20/25, 9:02 PM Linear Search - javatpoint
Home Python Java JavaScript HTML SQL PHP C#
DS Tutorial
DS Tutorial
DS Introduction
DS Algorithm
Asymptotic Analysis
DS Pointer
DS Structure
DS Array
DS Array
2D Array
DS Linked List
Linked List
Types of Linked List
Singly Linked List
Doubly Linked List
Circular Linked List
Circular Doubly List
https://www.javatpoint.com/linear-search 1/17
1/20/25, 9:02 PM Linear Search - javatpoint
Skip list in DS
DS Stack
DS Stack
Array Implementation
← prev next →
Linear Search Algorithm
In this article, we will discuss the Linear Search Algorithm. Searching is the process of
finding some particular element in the list. If the element is present in the list, then the
process is called successful, and the process returns the location of that element; otherwise,
the search is called unsuccessful.
Two popular search methods are Linear Search and Binary Search. So, here we will discuss
the popular searching technique, i.e., Linear Search Algorithm.
Linear search is also called as sequential search algorithm. It is the simplest searching
algorithm. In Linear search, we simply traverse the list completely and match each element
of the list with the item whose location is to be found. If the match is found, then the
location of the item is returned; otherwise, the algorithm returns NULL.
It is widely used to search an element from the unordered list, i.e., the list in which items are
not sorted. The worst-case time complexity of linear search is O(n).
The steps used in the implementation of Linear Search are listed as follows -
First, we have to traverse the array elements using a for loop.
In each iteration of for loop, compare the search element with the current array
element, and -
If the element matches, then return the index of the corresponding array
element.
If the element does not match, then move to the next element.
https://www.javatpoint.com/linear-search 2/17
1/20/25, 9:02 PM Linear Search - javatpoint
If there is no match or the search element is not present in the given array, return
-1.
Now, let's see the algorithm of linear search.
Algorithm
Linear_Search(a, n, val) // 'a' is the given array, 'n' is the size of given array, 'val' is the
value to search
Step 1: set pos = -1
Step 2: set i = 1
Step 3: repeat step 4 while i <= n
Step 4: if a[i] == val
set pos = i
print pos
go to step 6
[end of if]
set ii = i + 1
[end of loop]
Step 5: if pos = -1
print "value is not present in the array "
[end of if]
Step 6: exit
Working of Linear search
Now, let's see the working of the linear search Algorithm.
To understand the working of linear search algorithm, let's take an unsorted array. It will be
easy to understand the working of linear search with an example.
Let the elements of array are -
Let the element to be searched is K = 41
https://www.javatpoint.com/linear-search 3/17
1/20/25, 9:02 PM Linear Search - javatpoint
Now, start from the first element and compare K with each element of the array.
The value of K, i.e., 41, is not matched with the first element of the array. So, move to the
next element. And follow the same process until the respective element is found.
Now, the element to be searched is found. So algorithm will return the index of the element
matched.
Linear Search complexity
Now, let's see the time complexity of linear search in the best case, average case, and worst
case. We will also see the space complexity of linear search.
https://www.javatpoint.com/linear-search 4/17
1/20/25, 9:02 PM Linear Search - javatpoint
1. Time Complexity
Case Time Complexity
Best Case O(1)
Average Case O(n)
Worst Case O(n)
Best Case Complexity - In Linear search, best case occurs when the element we
are finding is at the first position of the array. The best-case time complexity of
linear search is O(1).
Average Case Complexity - The average case time complexity of linear search is
O(n).
Worst Case Complexity - In Linear search, the worst case occurs when the
element we are looking is present at the end of the array. The worst-case in linear
search could be when the target element is not present in the given array, and
we have to traverse the entire array. The worst-case time complexity of linear
search is O(n).
The time complexity of linear search is O(n) because every element in the array is compared
only once.
2. Space Complexity
Space Complexity O(1)
The space complexity of linear search is O(1).
Implementation of Linear Search
Now, let's see the programs of linear search in different programming languages.
Program: Write a program to implement linear search in C language.
#include <stdio.h>
https://www.javatpoint.com/linear-search 5/17
1/20/25, 9:02 PM Linear Search - javatpoint
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: Write a program to implement 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++)
{
https://www.javatpoint.com/linear-search 6/17
1/20/25, 9:02 PM Linear Search - javatpoint
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: Write a program to implement 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;
https://www.javatpoint.com/linear-search 7/17
1/20/25, 9:02 PM Linear Search - javatpoint
}
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: Write a program to implement 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
https://www.javatpoint.com/linear-search 8/17
1/20/25, 9:02 PM Linear Search - javatpoint
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: Write a program to implement 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)
https://www.javatpoint.com/linear-search 9/17
1/20/25, 9:02 PM Linear Search - javatpoint
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: Write a program to implement 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;
https://www.javatpoint.com/linear-search 10/17
1/20/25, 9:02 PM Linear Search - javatpoint
}
$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
So, that's all about the article. Hope the article will be helpful and informative to you.
Next Topic Binary Search
← prev next →
Related Posts
Binary Search
Algorithm In this article, we will discuss the Algorithm. Searching is the process of finding
some particular element in the list. If the element is present in the list, then the process is
called successful, and the process returns the location of that element. Otherwise,...
12 min read
https://www.javatpoint.com/linear-search 11/17
1/20/25, 9:02 PM Linear Search - javatpoint
Learn Important Tutorial
Python Java
Javascript HTML
Database PHP
C++ React
B.Tech / MCA
https://www.javatpoint.com/linear-search 12/17
1/20/25, 9:02 PM Linear Search - javatpoint
DBMS Data
Structures
Operating
DAA
System
Computer Compiler
Network Design
Computer Discrete
Organization Mathematics
Ethical Computer
Hacking Graphics
Web Software
Technology Engineering
https://www.javatpoint.com/linear-search 13/17
1/20/25, 9:02 PM Linear Search - javatpoint
Cyber
Automata
Security
C
C++
Programming
Java .Net
Python Programs
Control Data
System Warehouse
Preparation
https://www.javatpoint.com/linear-search 14/17
1/20/25, 9:02 PM Linear Search - javatpoint
Aptitude Reasoning
Verbal Interview
Ability Questions
Company
Questions
https://www.javatpoint.com/linear-search 15/17
1/20/25, 9:02 PM Linear Search - javatpoint
https://www.javatpoint.com/linear-search 16/17
1/20/25, 9:02 PM Linear Search - javatpoint
https://www.javatpoint.com/linear-search 17/17
