2. Suppose that you are given an unsorted array A of length n, in which all values are different re that A[i] A[i + 1] and Ali] Ali-1] ( f A. then it need only be less than the single adjacent element). In other words, Ali] is less than all adjacent values in A al numbers. A local manamum of A 1s an index 2 such If i s the first or last element Create an efficient algorithm for finding a local minimum in better than O(n) time. Note that you don't need to return all local minima- just one (Hint: Suppose you split the array in half, and compare the two boundary elements Aljl and Alj + 11. If Aljl Alj + 11. on which side are you quar- anteed to find a local minimum? What if A[j + 1]ADI? Why?) What is the running time of your algorithm