同時找最大與最小的下界（lower bound for max and min together）

單獨找最大值花 n-1 次比較；單獨找最小值也花 n-1 次。要兩者都得，懶辦法是各掃一遍，約 2n - 2 次比較。但你可以更聰明，而令人驚訝的答案是：同時找最大「與」最小只需要約 3n/2 次比較——最壞情況精確為 ceil(3n/2) - 2。這是一個可愛的例子：下界與一個並不顯然的最優演算法相吻合，遠低於天真的 2n。

聰明的演算法以「成對」處理元素。取兩個新元素，先彼此比較（1 次）；較小者是最小值的候選，較大者是最大值的候選。然後拿較小者與目前的最小比（1 次）、較大者與目前的最大比（1 次）。所以每一對元素只花 3 次比較就同時更新兩個極值，相較於各自獨立處理兩個極值所需的 4 次。這給出總共約 3n/2。相吻合的下界用一個對手，為每個元素追蹤它是否曾「贏過」一次比較、是否曾「輸過」。要認證最大值，除一個外每個元素都必須至少輸過一次；要認證最小值，除一個外每個元素都必須至少贏過一次。對手證明單次比較最多供應一個新的「曾輸」標籤與一個新的「曾贏」標籤，並計算還缺多少這種標籤，逼出約 3n/2 次比較。

兩個誠實要點。第一，精確界 ceil(3n/2) - 2 略微取決於 n 是偶是奇，因為配對時剩下那個元素的處理方式——乾淨的 3n/2 圖像是偶數情形。第二，如同此處所有結果，它是比較模型且最壞情況。真正的教訓是概念性的：合併兩個計算可以比分開做便宜，因為花在其中一邊的工作（成對比較）一兼二顧。認出這種「共享工作」正是打敗天真 2n 下界的關鍵，而對手論證認證了你無法做得比 3n/2 更好。