Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set.
How Linear Search Works?
Linear search works by comparing each element of the data structure with the key to be found. To learn the working of linear search in detail, refer to this post.
Pseudocode for Recursive Linear Search:
LinearSearch (array, index, key):
if index < 0:
return -1;
if item = key:
return index
return LinearSearch (array, index-1, key)
Implementation of Recursive Linear Search:
Below is the recursive implementation of linear search:
C
#include <stdio.h>
// Define a function to perform the linear search
int linearSearch(int arr[], int size, int key)
{
// If the size of the array is zero, return -1
if (size == 0) {
return -1;
}
// Check if the element at the current index
// is equal to the key
if (arr[size - 1] == key) {
// If equal, return the index
return size - 1;
}
// If not equal, call the function again
// with the size reduced by 1
return linearSearch(arr, size - 1, key);
}
// Driver code
int main()
{
int arr[] = { 5, 15, 6, 9, 4 };
int key = 4;
int index
= linearSearch(arr, sizeof(arr) / sizeof(int), key);
if (index == -1) {
printf("Key not found in the array.\n");
}
else {
printf("The element %d is found at %d index of the "
"given array \n",
key, index);
}
return 0;
}
C++14
// C++ Recursive Code For Linear Search
#include <bits/stdc++.h>
using namespace std;
int linearsearch(int arr[], int size, int key)
{
if (size == 0) {
return -1;
}
else if (arr[size - 1] == key) {
// Return the index of found key.
return size - 1;
}
return linearsearch(arr, size - 1, key);
}
// Driver Code
int main()
{
int arr[] = { 5, 15, 6, 9, 4 };
int key = 4;
// Function call
int ans = linearsearch(arr, 5, key);
if (ans == -1) {
cout << "The element " << key << " is not found."
<< endl;
}
else {
cout << "The element " << key << " is found at "
<< ans << " index of the given array." << endl;
}
return 0;
}
Java
// Java Recursive Code For Linear Search
import java.io.*;
class Test {
// Recursive Method to search key in the array
static int linearsearch(int arr[], int size, int key)
{
if (size == 0) {
return -1;
}
else if (arr[size - 1] == key) {
// Return the index of found key.
return size - 1;
}
return linearsearch(arr, size - 1, key);
}
// Driver method
public static void main(String[] args)
{
int arr[] = { 5, 15, 6, 9, 4 };
int key = 4;
// Function call to find key
int index = linearsearch(arr, arr.length, key);
if (index != -1)
System.out.println(
"The element " + key + " is found at "
+ index + " index of the given array.");
else
System.out.println("The element " + key
+ " is not found.");
}
}
Python3
# Python Program to Implement Linear Search Recursively
def linear_search(arr, size, key):
# If the array is empty we will return -1
if (size == 0):
return -1
elif (arr[size - 1] == key):
# Return the index of found key.
return size - 1
return linear_search(arr, size - 1, key)
# Driver code
if __name__ == "__main__":
arr = [5, 15, 6, 9, 4]
key = 4
size = len(arr)
# Calling the Function
ans = linear_search(arr, size, key)
if ans != -1:
print("The element", key, "is found at",
ans, "index of the given array.")
else:
print("The element", key, "is not found.")
# Code Contributed By - DwaipayanBandyopadhyay
# Code is modified by Susobhan Akhuli
C#
// C# Recursive Code For Linear Search
using System;
static class Test {
// Recursive Method to search key in the array
static int linearsearch(int[] arr, int size, int key)
{
if (size == 0) {
return -1;
}
else if (arr[size - 1] == key) {
// Return the index of found key.
return size - 1;
}
return linearsearch(arr, size - 1, key);
}
// Driver method
public static void Main(String[] args)
{
int[] arr = { 5, 15, 6, 9, 4 };
int key = 4;
// Method call to find key
int index = linearsearch(arr, arr.Length, key);
if (index != -1)
Console.Write("The element " + key
+ " is found at " + index
+ " index of the given array.");
else
Console.Write("The element " + key
+ " is not found.");
}
}
// This Code is submitted by Susobhan Akhuli
PHP
<?php
// PHP Recursive Code For Linear Search
// Recursive function to search key in the array
function linearsearch($arr, int $size, int $key)
{
if ($size == 0)
return -1;
else if ($arr[$size - 1] == $key)
// Return index
return $size - 1;
return linearsearch($arr, $size - 1, $key);
}
// Driver Code
$arr = array(5, 15, 6, 9, 4);
$i;
$size = count($arr);
$key = 4;
$ans = linearsearch($arr, $size, $key);
if ($ans != -1)
echo "The element ", $key, " is found at ", $ans,
" index of the given array.";
else
echo "The element ", $key, " is not found.";
// This code is submitted by Susobhan Akhuli
?>
Javascript
// JavaScript Recursive Code For Linear Search
let linearsearch = (arr, size, key) => {
if (size == 0) {
return -1;
}
else if (arr[size - 1] == key)
{
// Return the index of found key.
return size - 1;
}
return linearsearch(arr, size - 1, key);
};
// Driver Code
let main = () => {
let arr = [5, 15, 6, 9, 4];
let key = 4;
let ans = linearsearch(arr, 5, key);
if (ans == -1) {
console.log(`The element ${key} is not found.`);
} else {
console.log(
`The element ${key} is found at ${ans} index of the given array.`
);
}
return 0;
};
main();
// This code is contributed by Aman Singla...
Output
The element 4 is found at 4 index of the given array.
Complexity Analysis:
Time Complexity:
- Best Case: In the best case, the key might be present at the last index. So the best case complexity is O(1)
- Worst Case: In the worst case, the key might be present at the first index i.e., opposite to the end from which the search has started in the list. So the worst case complexity is O(N) where N is the size of the list.
- Average Case: O(N)
Auxiliary Space: O(1) as this is a tail recursion, so no recursion stack space is utilized.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
