Understanding Linear Search

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 does not exist.

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.

So, here let’s say we have to search 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

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 array as an input.

where n is no of elements in an array

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).

Frequently Asked Questions

Key Takeaways

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.

Check out more blogs on Binary Search to read more about these topics in detail. And if you liked this blog, share it with your friends!