![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
Linear Search Algorithm
Introduction
Searching is the process of finding a desired element from a collection of available elements. For example, searching for a particular contact number in a phone directory. Desired phone number is called target and the phone directory is called search space. Search algorithms designed to find whether the target exists in the search space or anything. The search space can be an array or a list or it can be a database.
To understand searching algorithms in clear, let us consider the search space is an array "a" which contains "n" elements and the desired element or target element which we want to search is "k".
In Linear Search, we traverse the array sequentially to and check if the element is matching with the given target element or not. If we find any element in the array that matches with the target element then the search process is successful and we return the index of the element in the array. If we don’t find any matching element in the array, the search process is unsuccessful and we return -1.
Algorithm
1Input : Array a[] of length n and k is the target element2Step 1 : Set index i to 0 (start index)3Step 2 : If i >= n return -1 (We reached end of the array and search is unsuccessful)4Step 3 : If a[i] is equal to k, return i (search process is successful)5Step 4 : Else increase i by 16Step 5 : Repeat Step2 (As still elements left in the array to compare)
Example
Let us understand the linear search algorithm using an example with dry run.
1Input: int[] a = {5, 2, 3, 4, 17, 21, 71, 10, 12, 14, 31} and k = 712output: 6
Code Implementation
- Java
- Python
1public class LinearSearch {23 // Method to search for given value k in an array4 public int search(int[] a, int k) {5 // loop through elements of array6 for (int i = 0; i < a.length; i++) {7 // Check the current element matching with target element8 // Match found, so return index of the element9 if (a[i] == k) {10 return i;11 }12 }13 // No match found, so return -1.14 return -1;15 }1617 public static void main(String[] args) {18 // search space19 int[] a = {5, 2, 3, 4, 17, 21, 71, 10, 12, 14, 31};20 // target element21 int k = 71;2223 int index = new LinearSearch().search(a, k);24 if (index == -1) {25 System.out.println("Target element is not found");26 } else {27 System.out.println("Target element found at index " + index);28 }29 }30}
Video Explanation
Complexity Analysis
Time Complexity
Best Case : O(1) If the first element of the array is matching with the target element , just in one comparison the search process gets successful and so time complexity will be O(1)
Worst Case : O(n) As there are n elements in the array, there might be a possibility that the target element might be at the end of the array or the target element does not exist in the given array. In both cases a total of n comparisons needed to get the search process to be completed. So time complexity in the worst case will be O(n).
Space Complexity
We don’t need any extra process during the process of the search algorithm. So space complexity will be O(1).