[Introduction To Algorithms] 第九堂: Medians and Order Statistics

這一講的是一群元素中，不用排序找出第幾大的問題。


















一開始講的是同時找最大最小，需要花得比較次數，直覺想是 2n-3 次，但其實只要 floor(3n/2)-2 次即可。9.1 利用狀態機 model了 Min-max problem 的lower bound。 p4~p10.

這個問題是選i小的問題，不用用到 nlog(n)的時間。基本上是學 quicksort 的 pivot 比較大小，不過 pivot 要小心的挑 。

9.3 就是講如何小心的挑，
先五個五個做 insertion sort，再找中位數，這是一個經典的演算法。