Linear Search

What is Linear Search?

Linear Search is a fundamental searching algorithm used to find a specific element within a collection of elements. When employing Linear Search, each element in the collection is inspected individually in a sequential order until the desired element is located. This approach is sometimes referred to as Sequential Search due to its step-by-step exploration of elements.

Algorithm for Linear Search:

The steps for linear search are as follows:

Start: Begin at the first element of the collection.
Compare: Check if the current element matches the desired element.
Found: If there is a match, return true or the index of the current element.
Move: If no match, move to the next element.
Repeat: Keep repeating steps 2-4 until the end of the collection.
Not found: If the desired element is not found after checking all elements, return that it's not in the array.ray.

How Does Linear Search Algorithm Work?

In Linear Search Algorithm,

Every element is considered as a potential match for the key and checked for the same.
If any element is found equal to the key, the search is successful and the index of that element is returned.
If no element is found equal to the key, the search yields “No match found”.

For example: Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30

Step 1: Start from the first element (index 0) and compare key with each element (arr[i]).

Comparing key with first element arr[0]. SInce not equal, the iterator moves to the next element as a potential match.

Compare key with arr[0]

Comparing key with next element arr[1]. SInce not equal, the iterator moves to the next element as a potential match.

Compare key with arr[1]

Step 2: Now when comparing arr[2] with key, the value matches. So the Linear Search Algorithm will yield a successful message and return the index of the element when key is found (here 2).

Compare key with arr[2]

Time Complexity:

Best Case: The best case happens when the key is found at the first index, making the complexity O(1).
Worst Case: The worst case occurs when the key is at the last index, opposite to where the search began. This results in a complexity of O(N), where N is the list's size.
Average Case: The average case complexity is O(N).

Auxiliary Space: The auxiliary space is O(1) because only one variable is used to iterate through the list; no other variables are needed.

Advantages of Linear Search:

Linear search can be used irrespective of whether the array is sorted or not. It can be used on arrays of any data type.
Does not require any additional memory.
It is a well-suited algorithm for small datasets.

Disadvantages of Linear Search:

Linear search is slow for large datasets because it has a time complexity of O(N).
It is not good for big arrays.

When to use Linear Search?

Use linear search for small datasets.
Use it when searching for data stored in continuous memory.