Consider the searching problem:

Input: A sequence of $n$ numbers $A = \langle a_1, a_2, . . . , a_n \rangle$ and a value $v$.

Output: An index $i$ such that $v = A_i$ or the special value $\text {NIL}$ if $v$ 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.

Pseudocode for LINEAR-SEARCH(A, v)

Loop invariant for the pseudocode will be:

At the start of the each iteration of the for loop of lines 1-3, the subarray $A[1..i − 1]$ consists of the elements that are not equal to $v$.

And here is how the three necessary properties hold for the loop invariant:

Initialization: Initially the subarray is empty. So, none of its’ elements are equal to $v$.

Maintenance: In $i$-th iteration, we check whether $A[i]$ is equal to $v$ or not. If yes, we terminate the loop or we continue the iteration. So, if the subarray $A[1..i - 1]$ did not contain $v$ before the $i$-th iteration, the subarray $A[1..i]$ will not contain $v$ before the next iteration (unless $i$-th iteration terminates the loop).

Termination: The loop terminates in either of the following cases,

• We have found index $i$ such that $v$ = $A_i$.
• We reached the end of the array, i.e. we did not find $v$ in the array $A$. So, we return $\text {NIL}$.

In either case, our algorithm does exactly what was required, which means the algorithm is correct.