**Searching-**

- Searching is a process of finding a particular element among several given elements.
- The search is successful if the required element is found.
- Otherwise, the search is unsuccessful.

**Searching Algorithms-**

Searching Algorithms are a family of algorithms used for the purpose of searching.

The searching of an element in the given array may be carried out in the following two ways-

- Linear Search
- Binary Search

In this article, we will discuss about Linear Search Algorithm.

**Linear Search-**

- Linear Search is the simplest searching algorithm.
- It traverses the array sequentially to locate the required element.
- It searches for an element by comparing it with each element of the array one by one.
- So, it is also called as
**Sequential Search**.

Linear Search Algorithm is applied when-

- No information is given about the array.
- The given array is unsorted or the elements are unordered.
- The list of data items is smaller.

**Linear Search Algorithm-**

Consider-

- There is a linear array ‘a’ of size ‘n’.
- Linear search algorithm is being used to search an element ‘item’ in this linear array.
- If search ends in success, it sets loc to the index of the element otherwise it sets loc to -1.

Then, Linear Search Algorithm is as follows-

**Linear_Search (a , n , item , loc)**

Begin for i = 0 to (n - 1) by 1 do if (a[i] = item) then set loc = i Exit endif endfor set loc = -1 End

**Time Complexity Analysis-**

Linear Search time complexity analysis is done below-

**Best case-**

In the best possible case,

- The element being searched may be found at the first position.
- In this case, the search terminates in success with just one comparison.
- Thus in best case, linear search algorithm takes O(1) operations.

**Worst Case-**

In the worst possible case,

- The element being searched may be present at the last position or not present in the array at all.
- In the former case, the search terminates in success with n comparisons.
- In the later case, the search terminates in failure with n comparisons.
- Thus in worst case, linear search algorithm takes O(n) operations.

Thus, we have-

Time Complexity of Linear Search Algorithm is O(n).
Here, n is the number of elements in the linear array. |

**Linear Search Efficiency-**

- Linear Search is less efficient when compared with other algorithms like Binary Search & Hash tables.
- The other algorithms allow significantly faster searching.

**Linear Search Example-**

Consider-

- We are given the following linear array.
- Element 15 has to be searched in it using Linear Search Algorithm.

Now,

- Linear Search algorithm compares element 15 with all the elements of the array one by one.
- It continues searching until either the element 15 is found or all the elements are searched.

Linear Search Algorithm works in the following steps-

**Step-01:**

- It compares element 15 with the 1
^{st}element 92. - Since 15 ≠ 92, so required element is not found.
- So, it moves to the next element.

**Step-02:**

- It compares element 15 with the 2
^{nd}element 87. - Since 15 ≠ 87, so required element is not found.
- So, it moves to the next element.

**Step-03:**

- It compares element 15 with the 3
^{rd}element 53. - Since 15 ≠ 53, so required element is not found.
- So, it moves to the next element.

**Step-04:**

- It compares element 15 with the 4
^{th}element 10. - Since 15 ≠ 10, so required element is not found.
- So, it moves to the next element.

**Step-05:**

- It compares element 15 with the 5
^{th}element 15. - Since 15 = 15, so required element is found.
- Now, it stops the comparison and returns index 4 at which element 15 is present.

To gain better understanding about Linear Search Algorithm,

**Next Article-** **Binary Search**

Get more notes and other study material of **Design and Analysis of Algorithms**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.