申論題

 Please Turn Over (there are mo ore questions on the next pages).
Answer the following questions in details.
11. (5 points) Given an array of n integers A = (a₁, a₂,.., a_n) (n ＞ 0), you are asked to find the maximum and minimum elements with minimum comparisons. A simple solution is to iteratively compare each element with current max and min. It takes 2n comparisons in total.

(a) (3 points) Devise an algorithm that requires less than 1.67n comparisons.