题目是这样的:有一个n个数的排序列表。给定 x,在排序列表中找到一个等于 x 的数字。这里我们假设 x 确实在列表中。有一个 oracle 可以对你的问题“是否 x>=y?”回答"is"或“否”。与正常的二进制搜索不同,oracle 允许对您的问题撒一次谎。解决这个问题最天真的方法是你向 oracle 询问每个问题两次。如果两个答案相同,就知道口语没有说谎。这个算法我们需要比较 2log_2(n) 次。但是这个问题要求我找到一种算法,该算法仅使用 log_2(n)+o(logn) 比较即可找到 x。
我很努力,但是失败了。谁能给我一些关于如何解决这个问题的建议?谢谢。
最佳答案
跟踪您所在的区间。如果您总共需要 k
个问题,请检查每个 sqrt( k)
步骤。在检查一致性时,您可以每个问题问两次以确定。如果您检测到不一致,请返回 sqrt(k)
步骤。您只会问 c*sqrt(k)
个额外的问题。
关于algorithm - 如何在一个谎言模型中进行二分查找?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9058354/