Cor*_*ein 7 algorithm search list binary-search
在今天编写一些代码时,我发生了一种情况,这种情况导致我编写了一种我以前从未见过的二进制搜索.这个二进制搜索是否有名称,它真的是一个"二进制"搜索吗？
首先,为了使搜索更容易理解,我将解释产生其创建的用例.
假设您有一个有序号码列表.系统会要求您在列表中找到最接近x的数字索引.
int findIndexClosestTo(int x);
findIndexClosestTo() 始终遵循此规则的呼叫:
如果最后的结果
findIndexClosestTo()是i,那么指数越接近i当前调用的结果的概率越大findIndexClosestTo().
换句话说,我们需要找到的索引更接近于我们找到的最后一个索引而不是它.
举个例子,想象一个在屏幕上左右走动的模拟男孩.如果我们经常查询男孩所在地的指数,那么很可能他就在我们找到他的最后一个地方附近.
鉴于上面的情况,我们知道最后的结果findIndexClosestTo()是i(如果这实际上是第一次调用该函数,i默认为列表的中间索引,为简单起见,尽管单独的二进制搜索找到第一个结果调用实际上会更快),并且该函数已被再次调用.给定新数字x,我们按照此算法查找其索引:
interval = 1;x,定位于i？如果是这样,返回i;x是高于还是低于i.(请记住,列表已排序.)interval指数移向方向x.x在新位置找到,请返回该位置.interval.(即interval *= 2)x,请返回interval索引,设置interval = 1,转到4.鉴于上述概率规则(在Motivation标题下),我认为这是找到正确索引的最有效方法.你知道更快的方法吗？
在最坏的情况下,您的算法是O((log n)^ 2).
假设您从0开始(间隔= 1),并且您寻找的值实际上位于位置2 ^ n - 1.
首先,您将检查1,2,4,8,...,2 ^(n-1),2 ^ n.哎呀,超过,所以回到2 ^(n-1).
接下来你检查2 ^(n-1)+ 1,2 ^(n-1)+ 2,...,2 ^(n-1)+ 2 ^(n-2),2 ^(n-1) + 2 ^(N-1).最后一个词是2 ^ n,所以哎呀,再次打捞.回到2 ^(n-1)+ 2 ^(n-2).
依此类推,直到你最终达到2 ^(n-1)+ 2 ^(n-2)+ ... + 1 == 2 ^ n - 1.
第一次超调采取了log n步骤.接下来采取(log n)-1步骤.下一步(log n) - 2步.等等.
所以,最糟糕的情况是,您采取了1 + 2 + 3 + ... + log n == O((log n)^ 2)步骤.
我认为,更好的想法是在第一次超调后切换到传统的二进制搜索.这将保留算法的O(log n)最坏情况性能,而当目标确实在附近时趋向于更快.
我不知道这个算法的名称,但我确实喜欢它.(奇怪的巧合,我昨天可以用它.真的.)