CLRS 3e 2.1-3

2.1-3 Consider the searching problem:

Input: A sequence of n numbers A = <a1; a2; : : : ;an> and a value .

Output: An index i such that  v = Ai or the special value NIL if  does not appear in A.

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

LINEAR SEARCH: (A, v)

1:        r=NIL  
2:        for i = 1 to A.length   
3:           if(A[i]=v)   
4:             r=i
5:             return r 
6:           end if
7:        end for 
8:        return r   

We run through the length of the array, if we find the element we return it.  If we've reached the end of the for loop and haven't returned the value, then it wasn't found.  So we return NIL.

Loop Invariant - At the start of every loop, r contains the index of the search value, or r contains the special value NIL.

Initialization - At the start of the loop i=1, there are no elements in A yet considered for comparison. Value of r is NIL, indicating correctly that v has not yet been found.

Maintenance - At the start of each loop, we know r will hold the value NIL since it's not been found.  If it has been found, we would exit the loop and return the index at which it was found.

Termination - If we've reached the end of the loop then by our maintenance condition r will have the the value NIL.  If we've found the value, we exit the loop by returning the value.