Linear Search

by codecrucks · Published 20/09/2021 · Updated 03/08/2022

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

Additional Reading: Wiki