Input: $A$, a sorted array of $n$ ints, and $x$, an int to search for

Output: $k$, an index such that $A[k] = x$, if one exists, and 'NOT FOUND' otherwise

i = 0 while i < n and A[i] < x i = i + 1 if i < n and A[i] == x return i else return 'NOT FOUND'

11 | 17 | 19 | 28 | 33 | 34 | 40 | 42 | 46 | 51 | 57 |

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

- When gallopSearch is called on array $A$ above searching
for $x = 34$, what are the values of
**i**,**left**and**right**immediately prior to the call to binarySearch in the last line of the algorithm? - When gallopSearch is called on array $A$ above searching
for $x = 53$, what are the values of
**i**,**left**and**right**immediately prior to the call to binarySearch in the last line of the algorithm? - When gallopSearch is called on array $A$ above searching
for $x = 19$, what are the values of
**i**,**left**and**right**immediately prior to the call to binarySearch in the last line of the algorithm?

In your definition, be precise and try not to use the word "max" but rather define it in terms of basic comparisons like greater-than or less-than.

percolateMax(A,n) /* A is an array of n integers */ i = 0 while i < n - 1 do if A[i] > A[i+1] swap(A[i],A[i+1]) i = i + 1 return A[n-1]

- Give a loop invariant for the "while" loop in this algorithm, i.e. a condition that is true every time test condition is evaluated, and which makes it easy to give a convincing argument that the algorithm is correct.
- Prove the loop invariant always holds: i.e. prove that it holds prior to the first loop iteration, and prove that assuming it holds at the beginning of a loop iteration, it must hold at the end of that loop iteration.
- Use the fact that the loop invariant is now proven to always hold to prove that percolateMax really is correct.