# Linear Search Proof of Correctness (trouble with case where $A[j] = v$ )

There's lots of answers on the proof but I didn't find anything that regarded my difficulty directly.

Question ( From " Introduction to Algorithms ( Cormen ) " ):

Answer ( Found on the net ):

I don't understand the case where $$A[j] = v$$ when we prove the maintenance step for before the j+1-th iteration ( after assuming $$A[j] \neq v$$ for before j-th iteration ). why does the loop invariant hold in such case?

I don't exactly see how it makes sense since the program terminates in such case and so we're left out without having proved that $$A[j] \neq v$$ for before the j+1-th iteration, but on the contrary we've shown that $$A[j] = v$$ for before the j+1-th iteration, hence contradicting the assumption that $$A[j] \neq v$$ for before j-th iteration.

• When A[j]=v you don't proceed to the next iteration. In that case the program returns i, which is equal to j. When the program exists through line 5 there is nothing to prove. Line 5 is inside the IF and therefore, the condition in it must be satisfied.
– plop
Feb 2, 2021 at 18:21
• What the paragraph is trying to prove is the assertion that when the program exits through line 8 then we know that A[k]!=v for all k<A.length. For this you need to assume that always the condition A[j]=v will not be satisfied.
– plop
Feb 2, 2021 at 18:27