“Linear Search” Explained in Simple Terms

Introduction

Hello, everyone! Let's have a look at the most fundamental and crucial Searching Algorithm, Linear Search. Linear Search is a search algorithm that aids in the discovery of an element in an array and returns the appropriate index. We may alternatively deliver a flag value to indicate that the element doesn't exist.

It's also known as Sequential Search since we're traversing our complete array progressively and comparing our target element to the current element at the current index. It works for both sorted and unsorted arrays, which is a huge plus.

Let’s talk about Algorithm

The following are the steps in this algorithm:

Step 1: Choose the first element to be the current one.

Step 2: Make a comparison between the current and target elements. If it's a match, move on to step 5.

Step 3: If the following element exists, set the current element to the next element and proceed to Step 2.

Step 4: The element you're looking for isn't there. Continue to Step 6.

Step 5: Locate the target element and return to it.

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

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

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

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

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

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

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

Step 6: Now, we encounter 15. 15 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.

We would return -1 (or any flag value) or false if the target element could not be located in the given array.

Let’s see the implementation of Linear Search in C++/Java/Python 

C++

#include

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: 5

Enter Numbers: 3 2 4 5 6

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

        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

        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: 8

Enter Numbers: 2 3 4 1 7 6 8 5

Enter a Number to Search: 6

Found at Index No. 5

Python

// Perform Linear Search

def linearsearch(arr, x):

   for i in range(len(arr)):

      if arr[i] == x:

         return i

      return -1

arr = [99, 2, 4, 55, 6, 10, 1, 77, 45, 34]

target_elem = 1 

print("Found at Index No. "+str(linearsearch(arr,target_elem)))

Output:

Found at Index No. 6

Time and Space Complexity

• Worst-case time complexity: O(N)

• Average case time complexity: O(N)

• Best case time complexity: O(1)

• Space complexity: O(1)

On average, linear search compares n/2 elements in a set, where n is the number of elements in the set. The linear search algorithm does n comparisons at most.

In the worst-case scenario, the linear search strategy requires 2n+1 comparisons (n to check if the target element is located and n+1 comparisons to determine if the list's end is reached). We can make n+1 comparisons in the worst case with optimizations.

Linear Search's Benefits and Applications

1. Both conceptually and in terms of implementation, it is fairly simple to grasp.

2. Both sorted and unsorted arrays are supported. It is independent of the order in which the array's members are arranged.

3. The searching process is done in O when the target element matches the first element in the array (1).

Conclusion

Sequential Search is another name for it. In it, we traverse our complete array in order and compare our target element to the current element at the current array index. Both sorted and unsorted arrays are supported. It has an O(1) time complexity in the best case, but an O(n) time complexity in the worst case, where n is the number of elements in an array.

Well, we tried to explain “how to use Linear Search on an array” in this blog in simple language. Hope you like it and get a better understanding of this concept.