Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a linear search method with an example?
2.1.
Example
3.
Linear Search Algorithm
4.
Implementation of Linear Search in C++/Java/Python
4.1.
C++
4.2.
Java
4.3.
Python
5.
Time and Space Complexity
6.
Types of Linear Search
7.
Advantages and Applications of Linear Search
8.
Disadvantages of Linear Search
9.
Frequently Asked Questions
9.1.
What is a linear search in Java?
9.2.
How is linear search used?
9.3.
What is the formula for linear search?
9.4.
Is linear search faster?
9.5.
Where is Linear Search used?
9.6.
Is linear search faster than binary?
10.
Conclusion
Last Updated: Apr 15, 2024
Easy

What is Linear Search?

Author Gunjan Batra
1 upvote

Introduction

Hi all! Let’s learn today about the most basic and important Searching Algorithm i.e. Linear Search

Linear Search is a searching algorithm that helps in finding the element in the array and returning the respective index. Additionally, we could also return a flag value to denote the element that does not exist.

Linear Search

It is also known as Sequential Search, as here, we sequentially traverse our entire array and compare our target element with the current element at the current index of our array. The best part is it works for both sorted and unsorted arrays.

What is a linear search method with an example?

Linear search is a simple sequential search algorithm where the main aim is to search for an element in the given list.

Example

  • Consider a list : [2,3,4,5,6,7], and we wish to search for element ‘6’. We can do this by traversing over the list and comparing the present number with the target value, i.e. 6.
     
  • We start from the beginning, i.e. element ‘2’, which is not equal to the target value ‘6’.Therefore we move forward.
     
  • Similarly, we can perform this step until the element is found. Ultimately we will stop our search at position 4, which contains the target value ‘6’.

Linear Search Algorithm

So, here let’s say we have to search for element 20 in our given array. 

We traverse the entire array one by one and compare 20 (our target element) with all elements of the array. 

Step 1: First, we encounter 12. 12 does not match with 20, and hence we proceed forward.

Step 2: Now, we encounter 5. 5 does not match with 20, and hence we proceed forward.

Step 3: Now, we encounter 10. 10 does not match with 20, and hence we proceed forward.

Step 4: Now, we encounter 15. 15 does not match with 20, and hence we proceed forward.

Step 5: Now, we encounter 31. 31 does not match with 20, and hence we proceed forward.

Step 6: Now, we encounter 20. 20 matches with our target element, and hence we return true, or the respective index(i.e., 5 here) depending upon our question and breaks from the loop.

In case the target element couldn’t be found in the given array, we would return -1(or any flag value) or false.

Implementation of Linear Search in C++/Java/Python

Let’s have a look at its implementations in various languages –

C++

#include<iostream>
using namespace std;
int main() {
    // Enter Input array
    int n = 0;
    cout<<"Enter size of array: ";
    cin >> n;
    int arr[n];
    cout<<"Enter Numbers: ";
    for(int i = 0; i < n; i++)
        cin>>arr[i];
 
    // Input the target element
    cout<<"\nEnter a Number to Search: ";
    int num;
    cin>>num;
 
    // Apply Linear Search
    int index = -1;  // -1 is the flag value
    for(int i = 0; i < n; i++){
        if(arr[i] == num){
            index = i;
            break;
        }
    }
    
    if (index == -1) cout << "\nElement not found";
    else cout<<"\nFound at Index No. "<< index;
    cout << endl;
    return 0;
}

Output:

Enter size of array: 10
Enter Numbers: 3 2 4 5 6 10 1 77 45 34
Enter a Number to Search: 5
Found at Index No. 3

Java

#import java.util.*;
 
public static void main(String[] args){
    Scanner s = new Scanner(System.in);  
    // Input size of array
    System.out.println("Enter size of array: ");
    int n = s.nextInt();  
 
    // Enter Input array
    System.out.println("Enter Numbers: ");
    for(int i=0; i<n; i++)
        arr[i] = s.next();
 
    // Input the target element
    System.out.println("Enter a Number to Search: ");
    int num = s.next();
 
    // Apply Linear Search
    int index = -1;  // -1 is the flag value
    for(int i=0; i<n; i++){
        if(arr[i]==num){
            index = i;
            break;
        }
    }
    if (index == -1) System.out.println(“Element not found”);
    else 
         System.out.println("Found the target element at Index No."+ index);
}

Output:

Enter size of array: 10
Enter Numbers: 3 2 4 5 6 10 1 77 45 34
Enter a Number to Search: 5
Found at Index No. 3

Python

// Perform Linear Search
def linearsearch(arr, x):
   for i in range(len(arr)):
      if arr[i] == x:
         return i
      return -1
 
arr = [3, 2, 4, 5, 6, 10, 1, 77, 45, 34]
target_elem = 5 
print("Found at Index No. "+str(linearsearch(arr,target_elem)))

Output:

Found at Index No. 3

Read About - Linear Search in C and Multithreading in java

Time and Space Complexity

Time Complexity:

Best Time Complexity : O(1) as if the element is present at 0th index, then only 1 comparison is required.

Average Time Complexity: It is the average of time complexities to find elements at every index i.e.


Comparisons required if target element at index 0 = 1
Comparisons required if target element at index 1 = 2
Comparisons required if target element at index 2 = 3
Comparisons required if target element at index 3 = 4
Comparisons required if target element at index n-1 = n
=> Average of Total Comparisons = (1+2+3….n)/n = O(n)

Worst Time Complexity: O(n) as if the target element is present at the last index or cannot be found. 

Space Complexity: O(1) as we aren’t utilizing or creating any space apart from the given space of the array as an input.

where n is no of elements in an array

Check out this array problem - Merge 2 Sorted Arrays

Read about also - Time & Space Complexity of Searching Algorithms

Types of Linear Search

Linear search is a simple sequential search algorithm. It is used when we need to find a specific element in a given list. 

  • Linear search in Array: Applying linear search in an array refers to iterating over an array and comparing each element with the target value.
     
  • Linear search in Linked list: You can apply linear search in a linked list by traversing over the linked list and comparing each node's value to the target value.
     
  • Linear search in Strings: Linear search in strings involves comparing each character in the string with the target character.

Advantages and Applications of Linear Search

  1. It’s extremely simple to understand both concepts-wise and implementation-wise.
     
  2. It works for both sorted and unsorted arrays. It does not depend on the arrangement of the elements in the array.
     
  3. When the target element matches the first element of the array, the searching work is done in O(1).

Also check out Addition of Two Numbers in Java here.

Disadvantages of Linear Search

  1. Linear search has higher time complexity as compared to another searching method known as binary search.
     
  2. Linear search requires a proper termination condition, else the loop will continue to check all the elements even if the key element is already detected.
     
  3. Linear search is not suitable for larger input values due to its high time complexity.

Check out this article - Difference between Linear Search and Binary Search

Frequently Asked Questions

What is a linear search in Java?

Linear search in Java is a method for finding an element in a list. In linear search, we traverse the list sequentially and check if that particular element is present or not.

How is linear search used?

Linear search is used for finding an element in a list by iterating over it and simultaneously checking if the element is present or not.

What is the formula for linear search?

The linear search in a list can be implemented by initializing a loop that iterates over the list. We can use the ‘if’ statement to check if the element is present or not.

Is linear search faster?

Linear search is slower as compared to binary search. The time complexity of the linear search is O(n), whereas the time complexity of the binary search is O(logn).

Where is Linear Search used?

It is used when elements are not given in sorted order or the arrangement of elements is not predefined.

Is linear search faster than binary?

Binary Search is faster than Linear Search as The worst-case time complexity of the Linear Search is O(N) while binary Search has O(log2N). But Binary search can only be applied if the array is sorted. However, there is no such condition for linear Search.

Conclusion

In this blog, we learned how to apply Linear Search to the given array. 

  • It is also known as Sequential Search.
     
  • In it, we sequentially traverse our entire array and compare our target element with the current element at the current index of our array.
     
  • It works for both sorted and unsorted arrays.
     
  • Its Best Case Time Complexity is O(1), but Worst Case Time Complexity is O(n), where n is the number of elements in an array.
Live masterclass