About the article
In this article, I will be taking you through one of the searching algorithms, Linear search, step by step and perform a complete analysis of it.
This technique of linear search works for both sorted and unsorted array. It follows a simple procedure but consumes a lot of time than binary search. It is also known as sequential search as it’s searched in a sequential manner.
Algorithm
Source: Tutorialspoint
- From the above gif, you can see that, you compare each and every element in array with the key (element to be searched for).
- If it’s present, we stop there and say it’s successful, else the element is not found.
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public class LinearSearch { public static int linearSearch(int[] inputArray,int key) //sort function { for(int i=0;i<inputArray.length;i++) { if(inputArray[i] == key) // if the array is equal to the element searched { return i; //return the index i.e position } } return -1; //not found } public static void main(String args[]) { int[] arr1 = {5,9,10,2,90,4}; int key = 2; //input key int result = linearSearch(arr1,key); System.out.println( (result != -1) ? "Required key:- "+key+" found at index:- "+result : "Key "+key+ " not found"); key = 18; //input key result = linearSearch(arr1,key); System.out.println( (result != -1) ? "Required key:- "+key+" found at index:- "+result : "Key "+key+ " not found"); } } |
Output
|
1 2 |
Required key:- 2 found at index:- 3 Key 18 not found |
Time complexity
If there are n elements in the array, the Base case needs only one comparison.
Hence the order is O(1).
In the worst case, we need n comparisons. Hence O(n) for the worst case.
Note: While stating the order we consider the worst case.
Hence the order of linear search is O(n)!
