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
- It’s extremely simple to understand both concepts-wise and implementation-wise.
- It works for both sorted and unsorted arrays. It does not depend on the arrangement of the elements in the array.
- 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
- Linear search has higher time complexity as compared to another searching method known as binary search.
- 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.
- 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.