Sorted Array

$(5$ points$)$

Suppose that you are given a sorted array $A$ of size $n$ that has been circularly shifted $k$ posi$-$

tions to the right. For example, $35,42,5,15,27,29$ is a sorted array that has been circularly

shifted $k=2$ positions, while $27,29,35,42,5,15$ has been shifted $k=4$ positions.

Suppose you do not know the value of $k.$ Give an $O(logn)$ algorithm to find the largest

number in $A.$

Description of the algorithm

$(3$ points$)$

Brief justification why the algorithm is correct

$(1$ point$)$

Brief justification why the algorithm runs in $O(logn)$ time

$(1$ point$)$