Linear search, the simplest search algorithm, is mainly used to find the element from an unordered list. It is also known by another name called sequential search algorithm. In linear search, the list is simply traversed, and each element in the list is matched with the element whose location needs to be found. When the searching process is done, it returns the location of the element, else the algorithm returns NULL. It has high complexity if the linear search is O(n).
Table of Contents
- Steps to Follow while Using a Linear Search Algorithm
- Algorithm
- Working on Linear Search
- Linear Search Complexity
- Application of Linear Search Algorithm
Steps to Follow while Using a Linear Search Algorithm
-
- Initially, we traverse the array of elements.
- Now compare the array element with the search element in each iteration –
o If it’s a correct match, then the index of the corresponding array element will return.
o If it doesn’t match, then it will switch to the next element.
- If the search element doesn’t exist in the array or there is no match, the given array returns -1.
Algorithm:
Linear Search (Array A, Value x)
- Step 1: Set i to 1
- Step 2: if i > n, then jump to step 7
- Step 3: if A[i] = x then jump to step 6
- Step 4: Set i to i + 1
- Step 5: Go to step 2
- Step 6: Print element x found at index i and jump to step 8
- Step 7: Print element not found
- Step 8: Exit
Working on Linear Search
Let’s understand the working of linear search with an example of an unsorted array:
Here we have an array of elements
Let K = 17 be the element to be searched
Now, we will compare K with each of the elements until we find K=17
The value of K is not matched with the first element of the array. So, we will switch to the next element and keep repeating the same step until K=17.
Now, as the element to be searched, i.e., K=17 is found, it will return the index of the matched element.
Linear Search Complexity
Time Complexity
| Case | Time Complexity |
| Best Case | O(1) |
| Average Case | O(n) |
| Worst Case | O(n) |
Space Complexity
| Space Complexity | O(1) |
Application of Linear Search Algorithm
- The linear search is applicable on both single and multi-dimensional arrays.
- It is less complex, effective, and easy to implement when the array contains a few elements.
- It is efficient when we need to search for a single element in an unordered array.
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
Comments