Array number comparision

1 Use the least number of comparisons to find the largetst and smallest number.

1 2 4 3 6 5 8 7

• Brute Force : for n .. max min => 2n
• 1 2 | 4 3 | 6 5 | 8 7
• Fist round: n/2
  • small 1 3 5 7 n/2
  • large 2 4 6 8 n/2
  • total comparision 3n/2 = 1.5n

2 How to use the least number of comparisions to find the largest and second largetst number?

1 2 4 3 6 5 8 7

        8 [2, 7, 4]
    4 [3, 1]    8 [2, 7]
3[2]    4[1]  7[5]       8[2]
3  2    1  4   5 7       2  8

每次找最大的时候，把第二可能大的值也带着！

• 1st large: 1*n
• 2nd large: log n