We want to write an algorithm that expects an array *A*[1*..n*] and a number *x*, and returns a number *q*, and that implements the specification **precondition **the array *A*[1*..n*] is non-decreasing, and we know that *x *occurs in *A*[1*..n*] **postcondition ***q *∈ 1*..n *and *A*[*q*] = *x*.

1 2 3 4 5 6

12 | 15 | 17 | 17 | 26 | 30 |

For example, if *A*[1*..*6] is given bythen

- if
*x*= 26 then*q*= 5 must be returned - if
*x*= 17 then either*q*= 3 or*q*= 4 must be returned (the specification is non-deterministic) - if
*x*= 10 then (as the precondition is not fulfilled) the algorithm could behave in any way; it may return 1, never terminate, or crash…

To implement this specification we shall use the binary search principle, and develop an iterative algorithm of the form

Find(*x,A,n*) *P q *← (*lo *+ *hi*) div 2 **while ***A*[*q*] 6= *x*

**if ***A*[*q*] *< x*

*T*

**else**

*E q *← (*lo *+ *hi*) div 2

**return ***q*

which uses variables *lo*, *hi*, and *q*, and where the loop invariant Φ has various parts:

*A*is non-decreasing- 1 ≤
*lo*≤*hi*≤*n* *lo*≤*q*≤*hi**x*occurs in*A*[*.hi*]

In this exercise, we shall develop *P *so as to complete the preamble, and develop *T *and *E *so as to complete the loop body.

**Specification**Translate the precondition into a formula in predicate logic (which must contain quantifiers, universal ∀ and/or existential ∃).**Preamble**We shall find a suitable*P*.- Give an example that shows that letting
*P*be*lo*← 1;*hi*←*n*− 1 may*not*establish Φ. - Now define
*P*(as a sequence of assignments) so that Φ will*always*be established (you don’t need to argue for that).

- Give an example that shows that letting
**Loop body**We shall find suitable*T*and*E*.- First consider the case where
*T*is given by*hi*←*q*and*E*is given by*lo*←*q*.

- First consider the case where

It is quite obvious that this choice will maintain parts (0)–(2) of Φ. But give an example that shows that this may *not *maintain part (3) of Φ.

- Next consider the case where
*T*is given by*lo*←*q*and*E*is given by*hi*←*q*.- Argue that this choice will maintain part (3) of Φ.
- Give an example that shows that with this choice, the loop may
*not*

- Write
*T*and*E*such that Φ is maintained*and*termination is ensured (you do not need to argue for these properties).

**Recursion (**Translate your completed iterative algorithm into a recursive algorithm that is equivalent, in that it always examines the*same*array elements.

Specifically, you must write a function Find that calls itself (but contains no **while **loop) and which as argument takes at least *lo *and *hi*, and *perhaps *also *q*, but you *may *omit the “global” *A *and *x*.

Remember also to state how to call Find at “top-level” so as to implement the specification.

## Reviews

There are no reviews yet.