※ 引述《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?