Consider the searching problem:
Input: A sequence of $n$ numbers $A = \langle a_1, a_2,\dots a_n \rangle$ and a value $v$
Output: An index $i$ such that $v=A[i]$ or the special value 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.
