从一个序列中获取最大和最小元素所需要的最小比较数

by Binqiang Zhao
这类问题一定要抓住比较最本质的内容，使用尽可能少的对算法形态的具体假设。
考虑一个n个元素组成的序列，需要从中找到最大元素max和最小元素min。
你能做的事情就是比较。
在比较之前，每个元素都有可能是最大元素和最小元素，因此max和min的候选分别为n个。总体候选数为2n。
比较就是减少候选，当候选减少到分别0个时，即是最终的解。
比较有三种：
1. 如果两个候选元素没参加过任何一次比较，那么对它们进行一次比较，较小的候选就仅仅是min的候选，较大的候选是max 的候选。min和max的候选个数分别减少1.
2. 对于已知是min的候选的元素，和min的当前值比较一次，min的候选个数减少1.
3. 对于已知是max的候选的元素，和max的当前值比较一次，max的候选个数减少1.
第1种比较可以进行的个数为floor(n/2)。
对于2、3两种情况，每个经过1的元素只能参加2和3之一，因此一次比较减少候选1. 这种比较的个数为ceiling(n/2) * 2 - 2 (其中两次比较已经蕴含在1中)。
对于初始的情况，可以选择两个元素进行比较，较大的赋给max，较小的赋给min。
因此，候选2n = floor(n/2) + ceiling(n/2)*2 - 2 = ceiling(3n/2) - 2。
这也是最小的比较次数。这里没限制你的算法如何设计，事实上，你无论如何设计算法，在最坏的情况下不会小于这个比较次数。这也是理论分析的美妙之处。