Consider the Linear search:

Input: A sequence of $n$ numbers $A=\{a_1,a_2,$dots,$a_n\}$ 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

Algorithm $2$ Linear$-$Search$($A$,$v$)$

$i=$NIL

for $j=1$ to A$.$length do

if $A[j]=v$ then

$i=j$

return $i$

end if

end for

return $i$

Use loop invariant to prove the correctness.