有序搜尋下界（sorted-search lower bound）

二分搜尋在 n 個元素的有序陣列中找目標，約用 log2(n) 次比較，每一步把範圍對半砍。它看似難以打敗——但它真的最優嗎？還是有更聰明的比較策略能找得更快？有序搜尋下界回答：任何基於比較的搜尋，在最壞情況下都無法做得比 Omega(log n) 次比較更好。二分搜尋不只是好；它在自己的模型裡就是可能達到的最佳。

論證是同一個決策樹計數的想法，現在用於搜尋。考慮搜尋一個不一定存在的值：演算法最終必須報告目標落入哪個「空隙」，或匹配到哪個位置。對 n 個有序元素，有 n 個可能的匹配位置，加上它們之間與兩端的 n+1 個空隙，所以搜尋可能必須回傳的相異答案至少有 n+1 個。把基於比較的搜尋建模成一棵二元決策樹：每個相異答案都需要自己的葉子，所以樹至少有 n+1 片葉子，因此樹高至少 log2(n+1)。既然最壞情況比較次數就是樹高，它至少是 log2(n+1) = Omega(log n)。每次比較最多給一個位元（是非），所以你無法用少於 log2(n+1) 個問題區分 n+1 個結果。

與排序相同的適用範圍提醒在此同樣成立。這是一個比較模型的陳述：它不禁止使用鍵值數值的更快搜尋，例如雜湊（期望 O(1) 查找）或內插搜尋（在均勻分佈鍵值上約 O(log log n) 次比較，靠猜測目標應在何處而非總是對半）。那些利用了次序以外的資訊，所以離開了比較競技場。但在純次序比較之內，Omega(log n) 是一塊真正的地板，而二分搜尋的 O(log n) 正好落在上面，給出 Theta(log n)。