Let A [1..n] be an array of integers, such that, for every 1 i We assume that A [1] = x, A [n] = y and that x < y.

The problem is as follows: from a value z, such that x z y, find an index j such that A [j] = z, if it exists.

a) Write an algorithm of complexity O (log n) using the technique "divide and conquer"; and that solves this problem. It is important to explain in detail your algorithm (idea) before writing the pseudo code.

b) Explain and prove in detail the complexity O (log n) of the algorithm in part a). [The only elementary operations involved in calculating the complexity of your algorithm are the comparisons made with z.]