Linear search, also known as sequential searching, is a straightforward algorithmic approach. It begins from one end of a list and inspects each element sequentially until the desired element is located. It represents the most basic form of searching algorithm.

• How it works?

Let's say we have a list of elements, and we're attempting to find a specific element, which we'll refer to as the "key."

The following steps are as follows to find key = 3.

Step 1: We begin by comparing the first element in the list, which is '5', with the key. Since the key, which is 3, is not equal to 5, we move on to the next element.

(3 ≠ 5)          

Step 2: Next, we compare the second element in the list, which is '8', with the key. Since the key, which is 3, is not equal to 8, we proceed to the next element.

(3 ≠ 8)

Step 3: Next, we compare the third element in the list, which is '10', with the key. Since the key, which is 3, is not equal to 10, we proceed to the next element.

(3 ≠ 10)

Step 4: Next, we compare the fourth element in the list, which is '3', with the key. Since the key, which is 3, is equal to 3, we found the element.

KEY

 

Otherwise, if the key is not found, it indicates that the key does not exist within the list.

• Linear Search Implementation

 

Example 1: Search for a number

Output:

3 is found at index 3

 

Example 2: Search for a string

Output:

Lee is found at index 3

 

• Time Complexity

In the linear Search, every element should be compared at least once. In the best-case scenario, the complexity is  when the key is found at the first index. Conversely, in the worst-case scenario, the complexity is  when the key is either found at the last index or not found at all.