Question

Question 2. (24 points. Recall that in Assignment 1, we developed recursive algorithms for implementing the specification Given a non-decreasing array Aſ1..n], and given a value v, return a number r such that • ifr=0 then v does not occur in A[1..n] • ifr #0 then 1 <r<n and A[r] = v. In this question, we shall implement this specification by an iterative algorithm, build around a while loop of the form (with AA, BB, CC and CC2 to be given later) AA while BB 94 (lo+hi) div 2 if A[g] =v found + true else if A[g] <u CC else CC2 if found return q else return 0 The while loop has an invariant with 3 parts: 1. 1 < lo and hi<n 2. if v occurs in A[1..n) then v occurs in Aſlo..hi] 3. if the boolean variable found is true then 1<o<n and A[g] = v.

Answer 1

Determine AA on the basis of given $\Phi$

Add statements to AA which initializes the conditions for while loop using the 3 given conditions.

1. 1 $\le$ lo and hi $\le$ n

Initially lo will at the start index and hi will be at the end index.

=> lo <- 1, hi <- n

2. If v occurs in A[1...n] then v occurs in A[lo...hi]

This condition also determines the above inferred information for AA, that the range of index for A is lo to hi.

And initiallly values for lo is 1 and for hi is n.

3. If the boolean variable found is true then $1 \le q \le n$ and A[q] = v

If found becomes true, then v is found in A array. Therefore, initially initialize found as false, so that as soon as v is encountered in A, found becomes true.

=> found <- false

Hence putting all initial conditions together,

AA = lo <- 1, hi <- n, found <- false