Q$1$: Prove the correctness of the following pseudocode of

Linear Search where $n$ is the number of elements in array

A using the loop invariant.

LinearSearch $,$ key$)$

$i=1$

while $in$ and $A[i]$ key

$i++$

if $in$

return true

else

return false