t[k] ≤t[i] for 0 ≤ k < i and t[k] >t[i] for i+1≤k In other words, find an index i such that all the elements to the left of t[i] are all smaller than or equal to t[i] and all elements on the right of t[i] are all larger than t[i]. Note that such an index may not exist, or there may be several indices that satisfy the condition. Here are a few examples: table [3, 6, 1,5] [4,0,8,-1,6, 15, 22, 19] [11, 8, 1, 4, 17, 26, 52, 25, 19, 55, 65, 60, 70, 100, 99] possible clues none 5 4,9,12 (a) (10 points) Find the algorithm linear in the worst case. Your algorithm doesn't have to give the highest value of the index found, but one of them, or -1 if no such index exists. Give the pseudo-code of your algorithm. (b) (4 points) Keep track of your algorithm with a few tables. (c) (5 points) Perform an asymptotic analysis of your algorithm. Response :
Fig: 1