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
Both conceptually and in terms of implementation, it is fairly simple to grasp.
Both sorted and unsorted arrays are supported. It is independent of the order in which the array's members are arranged.
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!