You are given an array A with n sorted numbers that has been circularly shifted k positions to the right. For example, consider the sorted array $\{5,15,27,29,32,45\}$; then $\{32,45,5,15,27,29\}$ is a sorted array that has been circularly shifted k$=2$ positions, while $\{27,29,32,45,5,15\}$ has been shifted k$=4$ positions. Suppose you do not know what k is$.$ Give a worst$-$case O$($logn$)$ time algorithm to find the largest number in A$.$ Prove correctness and provide a running time analysis.