# Linear Search

Linear search is a straightforward method of searching. It is sometimes referred to as **sequential search**. Assume A is an n-dimensional array. We wish to find an element in this array. This element will be referred to as a ‘Key.’

The Key is compared to each element of the array A one by one until the Key is discovered. The algorithm stops in two cases:

- when a key element is discovered or
- when the whole array is searched.

## Algorithm of Linear Search

The algorithm for linear search is given below :

**Algorithm** LINEAR_SEARCH(A, Key)
// Description: Perform a linear search on array A to search element Key
// Input: Array of length n and Key to be searched
// Output : Success / failure message
flag ← 0
**for** i ← 1 to n **do**
**if **Key == A[i] **then**
**print **“Element Found on Location”, i
flag ← 1
**break
end
end**
**if **flag == 0 **then**
print “Element Not Found”
**end**

## Complexity analysis of Linear Search

### Best Case:

If the key element is discovered in the first location, the algorithm just needs one comparison. A number of comparisons should be independent of array size in the best scenario. If the key is at the first place of the array, the method does one comparison regardless of the length of the array. As a result, the best case running time for linear searching is T(n) = O(1).

### Worst Case:

If the key element is at the last place or is not there at all, the algorithm performs the maximum number of comparisons. The array as a whole must be scanned. The number of comparisons grows linearly with the size of the array. As a result, the worst-case running time of the linear search is (n) = O(n).

The problem size is reduced by one on each iteration, and the method does one comparison. So recurrence for linear search can be defined as T(n) = T(n – 1) + 1. The solution to this recurrence also demonstrates that the linear search’s worst-case running time is O(n).

**Recurrence Equation:**

Let us solve the recurrence:

In every iteration, algorithm does one comparison and problem size is reduced by 1. Hence, the recurrence of linear search can be formulated as,

T(n) = 0, for n = 0

T(n) = T(n – 1) + 1, for n > 0

Let us solve this using iteration method,

T(n – 1) = T(n – 2) + 1

⇒ T(n) = [T(n – 2) + 1] + 1 = T(n – 2) + 2

T(n – 2) = T(n – 3) + 1

⇒ T(n) = [T(n – 3) + 1] + 2 = T(n – 3) + 3

After k iterations,

T(n) = T(n – k) + k

For k = n

T(n) = T(n – n) + n = T(0) + n

The cost of solving problem of size 0 is definitely 0, so T(0) = 0

Hence, T(n) = O(n)

### Average Case:

The average case occurs when an element is neither on the first location nor at last. The key element may be near to the beginning of array or maybe near to end, or it may be somewhere near to middle. On average, the algorithm does (n / 2) comparisons.

Thus, T (n) = O(n/2) = O(n)

**Suggested Reading:** Binary Search

## Example of Linear Search

**Example: Simulate the linear search algorithm on an array A {44, 22, 88, 11, 55, 33, 66, 77} with Key = 55.**

**Solution:**

Here, element to be searched is 55, so Key = 55.

Linear search scans the array one by one element, compare it with Key. If Key is found, the search stops, otherwise it scans the next element and compares with the key. Simulation of given data is shown below :

## Some Popular Problems Solved using Divide and Conquer

- Linear Search
- Binary Search
- Convex Hull
- Max-Min Problem
- Larger Integer Multiplication
- Strassen’s Matrix Multiplication
- Finding Exponent Problem
- Merge Sort
- Quick Sort

Additional Reading: Wiki