Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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" ?

share|improve this answer
add comment

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 $.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.