Suppose you are given an array A of n sorted numbers that has been circularly shifted k positions 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 know what k is. Give an O(1) algorithm to find the largest number in A.
• Suppose you do not know what k is. Give an O(lg n) algorithm to find the largest number in A. For partial credit, you may give an O(n) algorithm.