algorithm - 如何在一个谎言模型中进行二分查找？

Question

题目是这样的:有一个n个数的排序列表。给定 x，在排序列表中找到一个等于 x 的数字。这里我们假设 x 确实在列表中。有一个 oracle 可以对你的问题“是否 x>=y？”回答"is"或“否”。与正常的二进制搜索不同，oracle 允许对您的问题撒一次谎。解决这个问题最天真的方法是你向 oracle 询问每个问题两次。如果两个答案相同，就知道口语没有说谎。这个算法我们需要比较 2log_2(n) 次。但是这个问题要求我找到一种算法，该算法仅使用 log_2(n)+o(logn) 比较即可找到 x。

我很努力，但是失败了。谁能给我一些关于如何解决这个问题的建议？谢谢。

Answer 1

跟踪您所在的区间。如果您总共需要 k 个问题，请检查每个 sqrt( k) 步骤。在检查一致性时，您可以每个问题问两次以确定。如果您检测到不一致，请返回 sqrt(k) 步骤。您只会问 c*sqrt(k) 个额外的问题。