Linear Search Algorithm (with Code)

Shiksha Online
Updated on Dec 13, 2023 12:26 IST
Have you ever wondered how to find a specific item in a list without sorting it? The linear search
algorithm does just that, sequentially checking each element of the list until it finds the target
item or reaches the end of the list. This simple yet effective method is widely used when data is
unsorted or constantly changing. Let us understand more!

The linear search algorithm is a simple and straightforward method used to find a
particular element in a list. It works by sequentially checking each element of the list
until the desired element is found or the end of the list is reached.

Table of Content

What is Linear Search?

Implementation code in C, C++, Python, and Java

Simple Approach

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 C

C++

Python

Java

Improved Approach
C

C++

Python

Java

Which type of search is better, Linear Search or Binary Search?

What is Linear Search?

Linear search is the simplest type of searching. It is a sequential searching algorithm

where we start from one end and check every element of the list until the searched
element is found.

Implementation code in C, C++, Python, and Java

Here, we are going to implement Linear Search in C, C++, Python, and Java using two
approaches.
Simple Approach

Improved Approach

Simple Approach to Implement Linear Search

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 T ime Complexity: O(n)

Space Complexity: O(1)

C Program

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 Copy code

# include <st dio.h>

// Function to perform linear search

int search(int array[], int n, int x) {
f or (int i = 0; i < n; i++) {
if (array[i] == x) {
ret urn i; // Return the index where the element is found
}
}
ret urn -1; // Element not found
}

// Main function
int main() {
int array[] = {2, 4, 0, 8, 6, 10, 23, 1, 9};
int x = 23;
int n = sizeof (array) / sizeof (array[0]); // Calculate the number of elements in
the array

int result = search(array, n, x); // Perform the search

if (result == -1) {
print f ("Element not f ound");
} else {
print f ("Element f ound at index: %d", result );
}

ret urn 0;
}

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
Output

Element found at index: 6

C++ Program

Copy code

# include <iost ream>

using namespace st d;

// Function to perform linear search

int search(int array[], int n, int x) {
// Going through array sequentially
f or (int i = 0; i < n; i++) {
if (array[i] == x) {
ret urn i; // Return the index where the element is found
}
}
ret urn -1; // Element not found
}

// Main function
int main() {
int array[] = {2, 4, 7, 8, 0, 1, 9};
int x = 8;
int n = sizeof (array) / sizeof (array[0]); // Calculate the number of elements in
the array

int result = search(array, n, x); // Perform the search

if (result == -1) {
cout << "Element not f ound";
} else {

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 } else {
cout << "Element f ound at index: " << result ;
}

ret urn 0;
}

Output

Element found at index: 3

Pyt hon Program

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 Copy code

# Linear Search in Python

def linearSearch(array1, n, x):
# Going through array sequentially
f or i in range(0, n):
if array1[i] == x:
ret urn i
ret urn -1

# Test array and search element

array = [2, 4, 5, 6, 8, 0, 1, 9]
x=1
n = len(array)

# Perform the linear search

res = linearSearch(array, n, x)

# Output the result

if res == -1:
print ("Element not f ound")
else:
print ("Element f ound at index: ", res)

Output

Element found at index: 6

Java Program

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 Copy code

class LinearSearch {
public st at ic int linearSearch(int [] array, int x) {
int n = array.lengt h;
f or (int i = 0; i < n; i++) {
if (array[i] == x) {
ret urn i; // Return the index where the element is found
}
}
ret urn -1; // Element not found
}

public st at ic void main(St ring args[]) {

int [] array = {2, 4, 5, 8, 0, 1, 9};
int x = 8;
int result = linearSearch(array, x);

if (result == -1) {
Syst em.out .print ("Element not f ound");
} else {
Syst em.out .print ("Element f ound at index: " + result );
}
}
}

Output

Element found at index: 6

Improved Approach to Implementing Linear Search

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
Improve Linear Search Worst-Case Complexity – where the search_element is at the
end of the array.

C Program

Copy code

# include <st dio.h>

void search(int arr[], int lengt h, int Element ) {

int lef t = 0;
int posit ion = -1;

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 int right = lengt h - 1;

// Run loop from 0 to right

f or (lef t = 0; lef t <= right ;) {
// If search_element is found with left variable
if (arr[lef t ] == Element ) {
posit ion = lef t ;
print f ("Element f ound in Array at %d Posit ion wit h %d at t empt s\n",
posit ion + 1, lef t + 1);
break;
}

// If search_element is found with right variable

if (arr[right ] == Element ) {
posit ion = right ;
print f ("Element f ound in Array at %d Posit ion wit h %d at t empt s\n",
posit ion + 1, lengt h - right );
break;
}
lef t ++;
right --;
}

if (posit ion == -1)

print f ("Not f ound element in Array\n");
}

int main() {
int arr[] = {2, 4, 7, 8, 0, 1, 9};
int element = 1;
int lengt h = sizeof (arr) / sizeof (arr[0]); // Correct way to get the number of
elements in an array

search(arr, lengt h, element );

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 search(arr, lengt h, element );
}

Output

Element found in Array at 6 Position with 2 attempts

C++ Program

Copy code

# include <iost ream>

using namespace st d;

void search(int arr[], int lengt h, int Element ) {

int lef t = 0;
int posit ion = -1;
int right = lengt h - 1;

// Run loop from 0 to right

f or (lef t = 0; lef t <= right ;) {
// If search_element is found with left variable
if (arr[lef t ] == Element ) {
posit ion = lef t ;
cout << "Element f ound in Array at " << posit ion + 1 << " Posit ion
wit h " << lef t + 1 << " At t empt " << endl;
break;
}

// If search_element is found with right variable

if (arr[right ] == Element ) {
posit ion = right ;
cout << "Element f ound in Array at " << posit ion + 1 << " Posit ion
wit h " << lengt h - right << " At t empt " << endl;

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 wit h " << lengt h - right << " At t empt " << endl;
break;
}
lef t ++;
right --;
}

if (posit ion == -1)

cout << "Not f ound element in Array" << endl;
}

int main() {
int arr[] = {2, 4, 7, 8, 0, 1, 9};
int element = 0;
int lengt h = sizeof (arr) / sizeof (arr[0]); // Correctly calculate the length

search(arr, lengt h, element );

}

Output

Element found in Array at 5 Position with 3 Attempt

Pyt hon Program

Copy code

def search(arr, Element ):

lef t = 0
lengt h = len(arr)
posit ion = -1
right = lengt h - 1

# Run loop from 0 to right

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 # Run loop from 0 to right
while lef t <= right :
# If element is found with left variable
if arr[lef t ] == Element :
posit ion = lef t
print ("Element f ound in Array at ", posit ion + 1, "Posit ion wit h", lef t + 1,
"At t empt ")
break

# If element is found with right variable

if arr[right ] == Element :
posit ion = right
print ("Element f ound in Array at ", posit ion + 1, "Posit ion wit h", lengt h -
right , "At t empt ")
break

lef t += 1
right -= 1

# If element is not found

if posit ion == -1:
print ("Not f ound in Array wit h", lef t , "At t empt ")

# Driver code
arr = [1, 2, 3, 4, 5, 7, 8]
element = 5

# Function call
search(arr, element )

Output

Element found in Array at 5 Position with 3 Attempt

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
Java Program

Copy code

import java.io.*;

class Improved_LS {

public st at ic void search(int arr[], int Element ) {

int lef t = 0;
int lengt h = arr.lengt h;
int right = lengt h - 1;
int posit ion = -1;

// Run loop from 0 to right

f or (lef t = 0; lef t <= right ;) {

// If Element is found with left variable

if (arr[lef t ] == Element ) {
posit ion = lef t ;
Syst em.out .print ln("Element f ound in Array at "
+ (posit ion + 1) + " Posit ion wit h "
+ (lef t + 1) + " At t empt ");
break;
}

// If Element is found with right variable

if (arr[right ] == Element ) {
posit ion = right ;
Syst em.out .print ln("Element f ound in Array at "
+ (posit ion + 1) + " Posit ion wit h "
+ (lengt h - right ) + " At t empt ");
break;

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
 break;
}

lef t ++;
right --;
}

if (posit ion == -1)

Syst em.out .print ln("Not f ound in Array wit h "
+ lef t + " At t empt ");
}

public st at ic void main(St ring[] args) {

int arr[] = {1, 2, 3, 4, 5, 8, 9};
int element = 5;
search(arr, element );
}
}

Output

Element found in Array at 5 Position with 3 Attempt

Which type of search is better, Linear Search or Binary Search?

Linear search can be used on single and multidimensional arrays, whereas binary
search can only be implemented on the one-dimensional array. Linear search is less
efficient when we consider large data sets. Binary search is more efficient than linear
search in the case of large data sets.

However, actually, both types of searches have their own merits and demerits. The
answer to this question depends on the dataset entirely. If we’re searching for an
element present at the extreme ends of the list, then a Linear search will run better
than a binary search.

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.
Conclusion

Hope the above article helped you understand linear search better. If you have any
queries feel free to reach us at the link below. For more such articles, stay tuned to
Shiksha Online.

Disclaim e r: This PDF is auto -generated based o n the info rmatio n available o n Shiksha as
o n 14-Dec-20 23.