※ 引述《Leon (Achilles)》之銘言：
:
: 這題是考 怎麼找 Median, 你可以用 Quick Sort 的變形去找.
:
: 你先考慮一下簡單的題目:
: 要是有 9 cars, and has a run way with 3 laps
: How to do it?
:
: First round: do a run with 3 cars, we need 3 games.
:
: Second round: We pick the 'median' of the first round,
: thus, we will have `median of the median'.
:
: We call it X.
:
: Now, we are sure 3 cars are faster than X, 3 cars are slower than X.
: 2 cars are unknown.
:
: Third round will be X and 2 unkonws.
:
: 用這個 Median of Median 的原理, 你就能解那個 49 cars case.
: 我就留給你自己補完了.
:
:
:
:
:

其實我舉例的意思是數字小的就是比較快的 以game 123為例Third round會拿4 6 9來比 但都不是5th

you can draw a graph and it will become clearthe third round will tell 4 is the 4th of the cars

But how to tell which car is the 5th after third round

http://en.wikipedia.org/wiki/Selection_algorithm去讀 median of median 那一段

Median of Medians那段 看來主要是在講 Median of Medians保證大於及小於某固定比例的cases 不過看完之後還是無法釐清我原本的問題: L大完整的步驟到底是什麼?就第一篇回文 9 cars 的描述 我原本以為只要 Round 3 拿 X跟 2 unkonws 比完就可以知道哪輛車是 5th 不過就我舉的例子 Game 123 來看並非如此L大有空的話 可否好人做到底舉個 49 cars 的 worst case說明如何保證在 16 步之內找到 25th car?