# “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.

Perfect eLearning offers basic & advanced coding tutorials for people who want to learn how to code.

Topics:

1. Introducing the best basic coding courses online.

2. The benefits of taking coding courses online.

3. The top three coding courses online that you should check out.

4. How to get started with coding courses online.

5. The best way to learn to code online.

6. The future of coding courses online.

7. Introducing the basics of coding

8. The benefits of learning to code

9. Types of coding tutorials available

10. How to get started with coding

If you're looking to learn to code, there are a variety of ways you can go about it. But, if you're looking for the easiest and most efficient way to learn, then these 5 steps are the way to go:

1. Choose the right language.

2. Use coding boot camps.

3. Use online coding communities.

4. Use online coding tutorials.

5. Use online coding examples.

For more details, you can talk to our experts.

Perfect eLearning

Learn & Grow!

• • • • • • 