You are given an array S[1, . . . , n] of n (distinct) numbers, where the numbers in the array are arranged in increasing-increasing order, i.e., S[i] < S[i + 1] < < S[n] < S[1] < S[2] < . . . S[i 1], for some unknown index i. Give a recursive algorithm to search for a given element (say x) in the array S. If x is present in the array, the algorithm should return the index of the position where it is present, otherwise it should return 0. Your algorithm should take O(log n) comparisons. Give pseudocode of your algorithm, argue its correctness using mathematical induction, and show that your algorithm takes O(log n) comparisons (in the worst case)