Linear Search in Data Structure
Free Data Structures and Algorithms courses with real-time projects Start Now!!
Let us consider a scenario where you have to find a book in your personal stack of books. Assuming that the stack is not arranged in any order, the only way to find a book is to read the title of each book. And when you find the desired book you stop this process and don’t look into further books. This is a real-life example of linear search.
Linear Search
Linear search is the most basic search algorithm in the data structure. It is used to search any element in a linear data structure like arrays and linked lists. Linear Search algorithm compares the search element to each element of the Data Structure and returns the location of the element if found.
Method to use Linear Search
1. Start from the first element and compare each element with the search element.
2. If the element is found, return at which position element was found.
3. If the element is not found, return -1.
Algorithm for Linear Search
Steps for Linear search are as follows:
Linear_Search ( Array A [ n ], search_element x)
1: Set i to 1
2: if i > n then go to step 7
3: if A[i] = x then go to step 6
4: assign i+1 to i
5: Go to Step 2
6: Print Element x Found at index i and exit
7: display “element not found”
Pseudocode for Linear Search
procedure linear_search (array, value) for each item in the array if item == value return the item's index end if end for end procedure
Example of Linear Search
Input Array: {‘D’,’A’,’T’,’A’,’F’,’L’,’A’,’I’,’R’}
Search Element: ‘I”
Output:
Linear Search Implementation in C++
#include <iostream> using namespace std; int search(int arr[], int n, int x) { int i; for (i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } int main(void) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = search(arr, n, x); if (result == -1) cout << "Element is not present in array" else cout << "Element found at location " << result+1; return 0; }
Implementation of Linear Search in C
#include <stdio.h> int search(int arr[], int n, int x) { int i; for (i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } int main(void) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = search(arr, n, x); if(result == -1) printf("Element is not present in array") Else printf("Element is present at index %d", result); return 0; }
Linear Search Implementation in Java
class DataFlair { public static int search(int arr[], int x) { int n = arr.length; for (int i = 0; i < n; i++) { if (arr[i] == x) return i; } return -1; } public static void main(String args[]) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int result = search(arr, x); if (result == -1) System.out.print( "Element is not present in array"); else System.out.print("Element is present at index " + result); }
Implementation of Linear Search in Python
def search(arr, n, x): for i in range(0, n): if (arr[i] == x): return i return -1 arr = [2, 3, 4, 10, 40] x = 10 n = len(arr) result = search(arr, n, x) if(result == -1): print("Element is not present in array") else: print("Element is present at index", result)
Time Complexity of Linear Search
The worst-case time complexity of a linear search algorithm is O(n) since it compares the search element to all the elements in an array or linked list.
Due to this reason, linear search is not common since other algorithms like binary search and hash table perform search operations at a very fast rate.
Complexity | Best Case | Average Case | Worst Case |
Time Complexity | O(1) | O(n) | O(n) |
Space complexity | O(1) |
Conclusion
In this article, we witnessed the most basic searching technique used for small inputs. Linear search is used for small inputs sizes. We have some more efficient algorithms for large inputs that we will study in future articles.
The time complexity of the linear search algorithm for the worst case is very non-efficient and therefore is not used widely in the professional world.
You give me 15 seconds I promise you best tutorials
Please share your happy experience on Google