LINEAR SEARCH:
Linear search is the simplest method of searching. In this method, the element to be found is sequentially searched in the list (Hence also called sequential search). This method can be applied to a sorted or to an unsorted list. Hence, it is used when the records are not stored in order.
Principle :The algorithm starts its search with the first available record and proceeds to the next available record repeatedly until the required data item to be searched for is found or the end of the list is reached.
Algorithm :
Procedure LINEARSEARCH( A, N, K, P )
/ A is the array containing the list of data items
/ N is the number of data items in the list
/ K is the data item to be searched
/ P is the position where the data item is found
P -1
Repeat For I = 1 to N Step 1
If A[ I ] = K
Then
P I
Exit Loop
End If
End Repeat
End LINEARSEARCH
|
In the above algorithm, A is the list of data items containing N data items. K is the data item, which is to be searched in A. P is a variable used to indicate, at what position the data item is found. If the data item to be searched is found then the position where it is found is stored in P. If the data item to be searched is not found then -1 is stored in P, which will indicate the user, that the data item is not found.
Initially P is assumed -1. The data item K is compared with each and every element in the list A. During this comparison, if K matches with a data item in A, then the position where the data item was found is stored in P and the control comes out of the loop and the procedure comes to an end. If K does not match with any of the data items in A, then P value is not changed at all. Hence at the end of the loop, if P is -1, then the number is not found.
Example:
K Number to be searched : 40
i = 1
|
i =2
|
i = 3
|
i = 4
|
i = 5
|
i = 6
|
i = 7
|
i = 8
|
i = 9
|
i=10
|
45
|
56
|
15
|
76
|
43
|
92
|
35
|
40
|
28
|
65
|
K ≠ A[1]
| |||||||||
45
|
56
|
15
|
76
|
43
|
92
|
35
|
40
|
28
|
65
|
K ≠ A[2]
| |||||||||
45
|
56
|
15
|
76
|
43
|
92
|
35
|
40
|
28
|
65
|
K ≠ A[3]
| |||||||||
45
|
56
|
15
|
76
|
43
|
92
|
35
|
40
|
28
|
65
|
K ≠ A[4]
| |||||||||
45
|
56
|
15
|
76
|
43
|
92
|
35
|
40
|
28
|
65
|
K ≠ A[5]
| |||||||||
45
|
56
|
15
|
76
|
43
|
92
|
35
|
40
|
28
|
65
|
K ≠ A[6]
| |||||||||
45
|
56
|
15
|
76
|
43
|
92
|
35
|
40
|
28
|
65
|
K ≠ A[7]
45
|
56
|
15
|
76
|
43
|
92
|
35
|
40
|
28
|
65
|
K = A[8] P = 8 : Number found at position 8
Advantages:
1. Simple and straight forward method.
2. Can be applied on both sorted and unsorted list.
Disadvantages:
1. Inefficient when the number of data items in the list increases