问题是这样的:有一个n个数字的排序列表.给定x,在排序列表中找到一个等于x的数字.这里我们假设x确实在列表中.有一个神谕可以回答"是"或"否"你的问题"是否x> = y？".与普通二进制搜索不同,oracle可以对你的问题撒谎一次.解决这个问题的最天真的方法是你向oracle提出两次问题.如果两个答案是相同的,你知道orale不是说谎.我们需要这个算法比较2log_2(n)次.但是这个问题让我找到一个只能使用log_2(n)+ o(logn)比较找到x的算法.
我努力尝试但失败了.有人可以就如何解决这个问题给我一些建议吗？谢谢.