2. (10 pts.) Divide-and-conquer Let A[1...] be an array. It has n elements, and n > 3. We also know something about the array: the first element is smaller than the second element, and the last element is smaller than the second to last element. A location x is said to be uphigh if A[x] > Afx - 1) and A[x] > A[x + 1). For example, there are six uphighs in the following array. The uphighs are in boldface. 5,6,6,2,3,7,5,4,8,3,3,4,10,6 1 Observe that, given what we know about the first and last element, our array must always have at least one uphigh (think about why this is). The task is to find the location of an uphigh. If there are multiple uphighs, we only need to find the location of one. (a) Fill in the missing code lines in the code below so that it works to find the location of an uphigh in O(logn) time. Algorithm 2: FIND UPHIGH(A[1...), s.e) Result: Returns the location of an uphigh in the sub-array As..e]. To find the location of an uphigh in the whole array, you would call FINDUPHIGH(A,1,n). midt *+- Amid-1 y + Almid 2-Amid + 1] MISSING CODE LINES (b) Give the intuition behind why your algorithm is correct