Problem 7. An array A of n integers is called semi-sorted if it is increasing until some index and then decreasing afterwards. In other words, there is some index 1

A[i+1] for p A[i+1] then the maximum is in A[1, ... , i]. So we can start at i = n/2 and at each step compare A[i] with A[i+1]; and then recurse on one of the two subarrays (as described above). This takes O(log n) steps as each time with one comparison the size of the array we keep searching is divided by 2. Below is the pseudo-code for searching in an array A from index f to l. We call this with f = 1 and 1 = n. Note that by definition, a semi-sorted array must contain at least three elements, and when it has three, to be semi-sorted, the middle element must be greater than its neighboring elements. We can either use this as the case for termination, or continue to "divide to reach the case where the given array a singleton. semi-Sorted-search (A, 4,1) if f = 1 then return Alfl else mid= [(f +1)/2] if A[mid] > A[mid + 1] then semi-Sorted-search (A, f, mid) else semi-Sorted-search (A, mid +1,1) Then it remains to prove the correctness of the algorithm. We prove the following predicate by induc- tion: For any semi-sorted array A containing n pair-wise comparable elements, semi-sorted-search() correctly finds the maximum element of A. The work is left to you