Wednesday, July 3, 2013

Linear or Sequential Search Algorithm | Searching Algorithm

Linear or Sequential Search Algorithm is one of simplest search algorithms but no very efficient. The objective of linear search algorithm is to look through an array of data to find a particular item, x. The item, x, is compared to every item in the array from the first item to any stage where a match is found. If a match is not found then item x is not in the array and the solution is 0.

The Best and Worst Case for the Linear Search Algorithm
The Best Case for the linear search algorithm is when only one comparison is required between x and the array A[1], A[2],...A[n]. This occurs when x is the first term in the array.

The Worst Case occurs when algorithm requires n comparison. This occurs when x = A[n], or when x does not appear in the array.

The Linear Search Algorithm Pseudo Code
procedure linear search (x: integer, a(1), a(2), ...., a(n): distinct integers)
i := 1
while (i <= n and x != a(i) )
     i := i + 1
if (i <= n)
     then location := i
else
     location := 0
return location {location is the subscript of the term that equals x, or 0 if x is not found}

Simple Example:
X = 20
Array = 10, 100, 20, 50, 25, 5
x = 20
i = 1
n = 6 elements
x != a(1) = 10
     i = 1 + 1 = 2
x != a(2) = 100
     i = 2 + 1 = 3
x = a(3) breaks the while loop
i is 3 which is <= n which is 6
     then location = 3
return 3 {3 is the subscript of the term that equals x}

No comments:

Post a Comment