首先請注意以下幾點。
如果在 5,000 美元的區間內有 k 個人，那麼我們不需要更多的問題，因為我們不關心他們的順序。如果在 10,000 美元的區間內有 k 個人，那麼我們只需要一個額外的問題。如果在 20,000 美元的區間內有 k 個人，那麼額外問題的數量取決於 k。如果 k = 2，如果兩人都在同一個 10,000 美元的範圍內，我們只需要兩個額外的問題，否則只需要一個額外的問題；如果 k = 3，那麼在最壞的情況下，我們仍然只需要兩個額外的問題；對於 k >= 4，我們最多需要三個額外的問題，詢問第一個和第二個 10,000 美元區間，然後詢問 5,000 美元大小的子區間。
現在我們可以回答問題了。
關於支援科學新聞業
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保未來能夠持續產出關於塑造我們當今世界的發現和想法的具有影響力的故事。
1. 對於 200,000 美元，詢問除最後一個區間外的每個 40,000 美元區間
$0 - $40,000
$40,001 - $80,000
$80,001 - $120,000
$120,001 - $160,000
所以，假設每個 40,000 美元的區間（包括 160,000 美元 - 200,000 美元）都有 2 個名字——最壞的情況。我們將透過三個額外的問題找到他們的順序：有一個問題要問關於第一個 20,000 美元或第二個 20,000 美元。然後對於每個 20,000 美元的區間，有一個問題關於第一個 10,000 美元或第二個 10,000 美元。同樣，對於每個 5,000 美元的區間。因此，對於 0 美元 - 200,000 美元區間內的 10 個人，您至少需要 4 + (5*3) = 19 個問題。
2. 如果在 0 美元到 200,000 美元之間只有四個人，那麼首先詢問是否有人收入超過 160,000 美元。在最壞的情況下，沒有人。然後詢問關於 80,000 美元。在最壞的情況下，有兩個人低於這個數字，兩個人高於這個數字。然後對於每個 80,000 美元的區間，詢問關於一個 40,000 美元的區間（最壞情況：都在一個區間內），然後是一個 20,000 美元的區間（最壞情況：都在一個區間內），然後是一個 10,000 美元的區間（最壞情況：都在一個區間內），然後是 5,000 美元。因此，問題的總數為 2 + (2*4) = 10。
3. 首先詢問關於第一個 100 萬美元的區間。在最壞的情況下，較低的百萬美元區間和較高的百萬美元區間各有兩人。進一步將每個一半分解為 500,000 美元的區間、250,000 美元的區間、125,000 美元的區間，然後是 80,000 美元（在最壞的情況下）、40,000 美元、20,000 美元，以及再多兩個。這總共給出 1 + (2*8) = 17 個問題。
4. 關鍵的觀察結果，我們可以歸功於 Ivan Rezanka，是二分搜尋是一個很好的通用策略。例如，如果你的區間大小為 80,000 美元，你最好詢問關於 0 美元到 40,000 美元，然後如果至少有兩個人在這個區間內，你可以接下來詢問關於 0 美元到 20,000 美元。這給出的資訊與詢問關於 0 美元到 20,000 美元，然後是下一個 20,000.01 美元到 40,000 美元一樣多。此外，你可能很幸運，不需要更多的問題（如果該區間內只有一個人或沒有人）。當區間的大小不是 5,000 美元的 2 的冪次方時，分析變得更加棘手。但基本思想沒有改變。請參閱 Ivan 在這裡的分析：http://cs.nyu.edu/cs/faculty/shasha/papers/salariesivan.doc