如何在一个谎言模型中进行二分搜索？
问题是这样的：有一个由n个数字组成的排序列表。给定 x，在排序列表中找到等于 x 的数字。这里我们假设 x 确实在列表中。有一个神谕可以对你的问题“是否 x>=y？”回答“是”或“否”。与普通的二分搜索不同，预言机可以对你的问题撒谎一次。解决这个问题最简单的方法是向神谕询问每个问题两次。如果两个答案相同，你就知道口头禅没有说谎。这个算法我们需要比较 2log_2(n) 次。但是这个问题要求我找到一种算法，可以仅使用 log_2(n)+o(logn) 比较来找到 x 。
我很努力但失败了。有人可以给我一些关于如何解决这个问题的建议吗？谢谢。
the question is like this: there is a sorted list of n numbers. Given x, find a number which is equal to x in the sorted list. Here we assume that x is indeed in the list. There is an oracle that can answer "yes" or "no" to your question "whether x>=y?". Unlike normal binary search, the oracle is allowed to lie once to your question. The most naive way to solve this problem is you ask each question twice to the oracle. If the two answers are the same, you know that the orale is not lying. This algorithm we need compare 2log_2(n) times. But this question ask me to find an algorithm that can find x using only log_2(n)+o(logn) comparisons.
I tried very hard but failed. Can anybody give me some advice on how to solve this problem? Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
跟踪您所处的区间。如果您总共需要
k个问题，请检查每个sqrt(k)< 的一致性（您是否处于应有的区间） /代码> 步骤。在检查一致性时，您可以将每个问题问两次以确保确定。如果您发现不一致，请返回sqrt(k)步骤。您只会问c*sqrt(k)个额外问题。Keep track of the interval you are in. If you need a total of
kquestions, check for consistency (whether you are in the interval you are supposed to be) everysqrt(k)steps. While checking for consistency you may ask each question twice to be sure. If you detect inconsistency, go backsqrt(k)steps. You will be asking no more thanc*sqrt(k)additional questions.利用这样一个事实：在神谕撒谎之后，二分搜索会走错路，从那时起你就不会得到神谕的答案任何变化（总是
>=或总是<）。如果 Oracle 对log(log(n))步骤的回答没有变化，请检查间隔一致性。如果当前间隔不一致，则再次询问oracle，如果仍然不一致，则返回log(log(n)) + 1步，继续正常的二分查找。此过程平均需要
O(log(log(n)))一致性检查以及最多log(log(n))额外的二分搜索步骤。平均附加问题数为
c*log(log(n))，最大附加问题数为log(n) / (log(log(n))) + log(log (n))。Use the fact that after the oracle lied, binary search goes wrong way, and you get no change in the oracle's answer since that time (always
>=or always<). If you get no change in the oracle's answer forlog(log(n))steps, check for interval consistency. If current interval is inconsistent, ask the oracle once more, and if still inconsistent, go backlog(log(n)) + 1steps and continue with normal binary search.This procedure requires
O(log(log(n)))consistency checks on average and up tolog(log(n))additional binary search steps.Average number of additional questions is
c*log(log(n)), maximum number of additional questions islog(n) / (log(log(n))) + log(log(n)).只问神谕这个问题：“x >= y 吗？”在二分搜索的每次迭代中一次。
如果你两次得到相同的答案，那么你就知道神谕第一次没有说谎。
例如，您正在搜索 x = 1，并且您针对 y = a 进行的第一个测试测试，并且预言机回答 x <一个。在第二个测试中，您针对 y = b 进行测试，并且预言机回答 x < b.由于您使用的是二分搜索，并且 oracle 说“<”，并且数组已排序，因此您知道 b <>一个。因此，如果x＜1，则b，你也知道 x < a，第一个答案不是谎言。如果第二个答案是谎言，且 x > b，那么 x < 仍然成立。 a，因为神谕只能说谎一次。
即使答案不是连续出现的，这也是事实。例如，您会得到三个答案：x < a，x≥b，x＜ c，你知道 c < a，通过二分查找，所以 x < 一定是正确的。 a，当神谕告诉你这些时，他并没有说谎。
那么当神谕说谎时会发生什么呢？如果谎言是 x < y，那么事实是 x >= y。因此，当你继续二分查找时，从那时起，你检查的数字都将太小，答案将永远是“> =”，直到你到达二分查找的底部。那时，您意识到如果神谕撒了谎，那么他上次告诉您除“> =”以外的内容时也撒了谎。因此，您在神谕对您撒谎并说“x < y”的地方重新开始二分搜索。
这将始终使用 < 2 log_2 n 比较，但是如果神谕在搜索开始时对你撒谎，那么你将不得不重复几乎 log_2 n 的工作，因此你不会得到你正在寻找的 log_2 n + o(log n) 答案。因此，您应该采纳 nm 建议的想法。如果你得到相同的答案，连续说 sqrt(log n) 次，那么你怀疑预言机可能对你撒了谎，并且你立即重新问你在答案开始重复之前提出的问题，而不是等待直到二分查找的底部。遵循这个策略，在最坏的情况下，你将重新问一个问题 log n / sqrt(log n) 次，并且你总是会发现谎言，最多浪费 sqrt(log n) 次工作，从而达到你原来的运行时间寻找。
Only ask the oracle the question: "is x >= y?" once on each iteration of your binary search.
If you get the same answer twice, then you know the oracle didn't lie the first time.
For example, you are searching for x = 1, and the first test you test against y = a, and the oracle answers x < a. On the second test you test against y = b and the oracle answers x < b. Since you are using binary search, and the oracle said '<', and the array is sorted, you know that b < a. Therefore, if x < b, you also know that x < a, and the first answer was not a lie. If the second answer is a lie, and x > b, then it is still true that x < a, since the oracle can only lie once.
This is true even if the answers don't come back to back. For example you get three answers: x < a, x >= b, x < c, you know that c < a, by your binary search, and so it must have been true that x < a, and the oracle wasn't lying when he told you that.
So what happens when the oracle does tell a lie? If the lie was x < y, then the truth was x >= y. Therefore, when you continue your binary search, from that point on, the numbers you check will all be too small, and the answer will always be ">=", until you reach the bottom of the binary search. At that point, you realize that if the oracle lied, he lied the last time he told you something other than ">=". So you restart your binary search at the point where the oracle lied to you and said "x < y".
This will always use < 2 log_2 n comparisons, but if the oracle lies to you at the beginning of the search, then you will have to repeat nearly log_2 n work, and so you don't get log_2 n + o(log n) answer you were looking for. Thus, you should incorporate the idea suggested by n.m.. If you get the same answer, say sqrt(log n) times in a row, then you suspect that the oracle may have lied to you, and you immediately re-ask the question you asked right before the answers started repeating, instead of waiting until the bottom of the binary search. Following this strategy, you will re-ask a question log n / sqrt(log n) times in the worst case, and you will always catch the lie with at most sqrt(log n) wasted work, which achieves the running time you were looking for.
您可能想要更改经典的二分搜索以使其正常工作，尝试在每次迭代中要求预言机比较数组的 2 个不同索引而不是仅 1 个，例如：
我认为这很明确，但可能是错误的。
它的复杂度与原来的BS相同，但比询问oracle两次或更多次要好。请注意，除非预言说谎，否则一个元素永远不会被比较两次，因此如果它出现一次甚至 k 次（其中 k 很小 -o(logn)），那么我们就可以了。
你可以去你最喜欢的编码环境，尝试编码，每次比较，算一下。尝试这个和天真的，并比较结果，如果我没有弄错的话，天真的应该比较这个的两倍。
请注意，我对索引不太仔细，您需要做一些思考以确保我没有丢失索引或没有意外重复索引。
You may want to change the classic binary search for this to work, how about try to ask the oracle in each iteration to compare 2 diffrent indexes of the array instead of just 1, something like:
I think that nails it, might be wrong tho.
it's complexity is the same as the original BS, but it is better then asking the oracle twice or more. notice that an element never gets compared to twice unless the oracle lies, so if it lies once or even k times where k is small-o(logn) then we are fine.
you may go to your favourite coding enviroment and try to code it, every time a comparison made, count it. try both this and the naive, and compare result, if im not mistaken, the naive should compare twice as much as this.
Notice tho, i was not too carefull with the indexes, you'll need to do some thinking to make sure i wasnt missing an index or wasnt repeating an index accidently.
我想在
3 * log(n)中解决这个问题可能很容易，只需在每一步问三次不等式问题，并且决定是多数决定。I guess solving this question in
3 * log(n)can be easy, by asking the inequality question three times at every step, and the decision is the majority one.