lit*_*ath 10 algorithm binary-search
问题是这样的:有一个n个数字的排序列表.给定x,在排序列表中找到一个等于x的数字.这里我们假设x确实在列表中.有一个神谕可以回答"是"或"否"你的问题"是否x> = y？".与普通二进制搜索不同,oracle可以对你的问题撒谎一次.解决这个问题的最天真的方法是你向oracle提出两次问题.如果两个答案是相同的,你知道orale不是说谎.我们需要这个算法比较2log_2(n)次.但是这个问题让我找到一个只能使用log_2(n)+ o(logn)比较找到x的算法.
我努力尝试但失败了.有人可以就如何解决这个问题给我一些建议吗？谢谢.
跟踪您所处的区间。如果您需要总共k问题，请检查每个步骤的一致性（您是否处于应有的区间）sqrt(k)。在检查一致性时，您可以将每个问题问两次以确保确定。如果发现不一致，请返回sqrt(k)步骤。您只会问c*sqrt(k)额外的问题。