Problem 3 (20 points) Suppose you are given an array of distinct numbers which was sorted and then rotated

indices for some unknown integer between 1 and 1. That is, you are given an array [1..]

such that some prefix [1..] is sorted in increasing order, and the corresponding suffix [ + 1..]

is also sorted in increasing order, and []

16-element array (where = 10): [9, 13, 16, 20, 21, 24, 25, 26, 27, 30, ||, 1, 2, 3, 5, 6, 8]

3.1 Describe and analyze an algorithm to compute the value of in (log) time.

3.2 Describe and analyze an algorithm to determine if the given array contains a given number

that runs in (log) time, assuming you already know the value of .

lem 3 (20 points) Suppose you are given an array of n distinct numbers which was sorted and then rotated k indices for some unknown integer k between 1 and n1. That is, you are given an array A[1..n] such that some prefix A[1..k] is sorted in increasing order, and the corresponding suffix A[k+1..n] is also sorted in increasing order, and A[n]