Linear Search Algorithm (with Code)

Linear Search Algorithm (with Code)

7 mins read931 Views 1 Comment
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?

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.

  1. Simple Approach
  2. Improved Approach

Simple Approach to Implement Linear Search

 

  • Time Complexity: O(n)
  • Space Complexity: O(1)

C Program


 
#include <stdio.h>
// Function to perform linear search
int search(int array[], int n, int x) {
for (int i = 0; i < n; i++) {
if (array[i] == x) {
return i; // Return the index where the element is found
}
}
return -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) {
printf("Element not found");
} else {
printf("Element found at index: %d", result);
}
return 0;
}
Copy code

Output

Element found at index: 6

C++ Program


 
#include <iostream>
using namespace std;
// Function to perform linear search
int search(int array[], int n, int x) {
// Going through array sequentially
for (int i = 0; i < n; i++) {
if (array[i] == x) {
return i; // Return the index where the element is found
}
}
return -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 found";
} else {
cout << "Element found at index: " << result;
}
return 0;
}
Copy code

Output

Element found at index: 3

Python Program


 
# Linear Search in Python
def linearSearch(array1, n, x):
# Going through array sequentially
for i in range(0, n):
if array1[i] == x:
return i
return -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 found")
else:
print("Element found at index: ", res)
Copy code

Output

Element found at index:  6

Java Program


 
class LinearSearch {
public static int linearSearch(int[] array, int x) {
int n = array.length;
for (int i = 0; i < n; i++) {
if (array[i] == x) {
return i; // Return the index where the element is found
}
}
return -1; // Element not found
}
public static void main(String args[]) {
int[] array = {2, 4, 5, 8, 0, 1, 9};
int x = 8;
int result = linearSearch(array, x);
if (result == -1) {
System.out.print("Element not found");
} else {
System.out.print("Element found at index: " + result);
}
}
}
Copy code

Output

Element found at index:  6

Improved Approach to Implementing Linear Search

Improve Linear Search Worst-Case Complexity – where the search_element is at the end of the array.

 

C Program


 
#include <stdio.h>
void search(int arr[], int length, int Element) {
int left = 0;
int position = -1;
int right = length - 1;
// Run loop from 0 to right
for (left = 0; left <= right;) {
// If search_element is found with left variable
if (arr[left] == Element) {
position = left;
printf("Element found in Array at %d Position with %d attempts\n", position + 1, left + 1);
break;
}
// If search_element is found with right variable
if (arr[right] == Element) {
position = right;
printf("Element found in Array at %d Position with %d attempts\n", position + 1, length - right);
break;
}
left++;
right--;
}
if (position == -1)
printf("Not found element in Array\n");
}
int main() {
int arr[] = {2, 4, 7, 8, 0, 1, 9};
int element = 1;
int length = sizeof(arr) / sizeof(arr[0]); // Correct way to get the number of elements in an array
search(arr, length, element);
}
Copy code

Output

Element found in Array at 6 Position with 2 attempts

C++ Program


 
#include <iostream>
using namespace std;
void search(int arr[], int length, int Element) {
int left = 0;
int position = -1;
int right = length - 1;
// Run loop from 0 to right
for (left = 0; left <= right;) {
// If search_element is found with left variable
if (arr[left] == Element) {
position = left;
cout << "Element found in Array at " << position + 1 << " Position with " << left + 1 << " Attempt" << endl;
break;
}
// If search_element is found with right variable
if (arr[right] == Element) {
position = right;
cout << "Element found in Array at " << position + 1 << " Position with " << length - right << " Attempt" << endl;
break;
}
left++;
right--;
}
if (position == -1)
cout << "Not found element in Array" << endl;
}
int main() {
int arr[] = {2, 4, 7, 8, 0, 1, 9};
int element = 0;
int length = sizeof(arr) / sizeof(arr[0]); // Correctly calculate the length
search(arr, length, element);
}
Copy code

Output

Element found in Array at 5 Position with 3 Attempt

Python Program


 
def search(arr, Element):
left = 0
length = len(arr)
position = -1
right = length - 1
# Run loop from 0 to right
while left <= right:
# If element is found with left variable
if arr[left] == Element:
position = left
print("Element found in Array at", position + 1, "Position with", left + 1, "Attempt")
break
# If element is found with right variable
if arr[right] == Element:
position = right
print("Element found in Array at", position + 1, "Position with", length - right, "Attempt")
break
left += 1
right -= 1
# If element is not found
if position == -1:
print("Not found in Array with", left, "Attempt")
# Driver code
arr = [1, 2, 3, 4, 5, 7, 8]
element = 5
# Function call
search(arr, element)
Copy code

Output

Element found in Array at 5 Position with 3 Attempt

Java Program


 
import java.io.*;
class Improved_LS {
public static void search(int arr[], int Element) {
int left = 0;
int length = arr.length;
int right = length - 1;
int position = -1;
// Run loop from 0 to right
for (left = 0; left <= right;) {
// If Element is found with left variable
if (arr[left] == Element) {
position = left;
System.out.println("Element found in Array at "
+ (position + 1) + " Position with "
+ (left + 1) + " Attempt");
break;
}
// If Element is found with right variable
if (arr[right] == Element) {
position = right;
System.out.println("Element found in Array at "
+ (position + 1) + " Position with "
+ (length - right) + " Attempt");
break;
}
left++;
right--;
}
if (position == -1)
System.out.println("Not found in Array with "
+ left + " Attempt");
}
public static void main(String[] args) {
int arr[] = {1, 2, 3, 4, 5, 8, 9};
int element = 5;
search(arr, element);
}
}
Copy code

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.

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.

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio

Comments

(1)

Write programme to maintain an doubly linekd list?

Reply to Ruchi Gour