# Proof of linear search?

Consider the searching problem:

Input: A sequence of $n$ numbers $A=(a_1, a_2, \ldots , 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$

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.

The algorithm is clearly very simple to prove. However could someone prove the correctness of the algorithm using a loop invariant? Note the "three necessary properties" are:

• Initialization: It is true prior to the first iteration of the loop.

• Maintenance: If it is true before an iteration of the loop, it remains true before the

• Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

-
What about using a "goal" variable initialized to NIL and taking as invariant "After iteration i, the goal variable contains an index $0 \leq j < i$ such that $A[j] = v$ if there exists one (in the range $\{0, \cdots, i - 1\}$), or NIL otherwise" ?
It's impossible to prove unless you state the algorithm. But, let's say your algorithm maintain a candidate index $j$ for loop iteration, which is update to $j \leftarrow j+1$, if $v_j \neq v$, and if the loop termination depends on $j$ not updating or reaching $n$ and the output is $j$, then you could say that a valid loop invariant is $v_i \neq v_j$ for $1 \leq i < j \le n$.