首先请注意以下几点。
如果在 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