Possible Duplicate:Proof of linear search? I'm reading the MIT Press, Introduction to Algorithms textbook 3rd edition, and I am a bit confused by an exercise. 2.1-3Consider the searching problem:Input: A sequence of n numbers A =  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 your loop invariant fulfills the three necessary properties.Earlier in the book I read that We must show three things about a loop invariant: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 thenext iteration.Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.I wrote this as my pseudocodeindex = nilj = 1 while j <= A.length and index == nil  if A[j] == v    index = j  j = j + 1But when it comes to proving using a loop invariant I have no idea what to do. What do I even use as a loop invariant? To be honest I'm not really clear about the entire loop invariant concept. Can someone please help me understand this? Thanks.
loop invariant proof
algorithms;algorithm analysis;correctness proof;loop invariants