边缘寻找二进制搜索

想象一下，使用条形图每天仅以图形形式发布每日通勤者人数的网站。我想通过在将图形保存为图像后读取条形图来确定数字（图像内容在此不重要）。我想要读取条形图的方法是通过寻找一个像素号（＃号通勤者轴）并提出问题：“像素是在”还是“关闭”？（On表示条存在并且off表示该猜测太高）注意：存在0的下界，并且在技术上是无限上界。但是，实际上，10000可能是现实的上限。另请注意，昨天没有变化是一个频繁发现。边缘寻找二进制搜索

给出一个从昨天开始的猜测数字，找出这个数字的最有效方法是什么？高效率意味着最少数量的查询来询问像素是打开还是关闭。

（要我非CS的眼睛，这似乎像一些排序边找到二进制搜索，但没有一个预先定义的数组。我可以说我已经学到了很多关于搜索）

我的算法作为一个函数。任何建议是最受欢迎的。

def EdgeFind(BlackOrWhite,oldtrial,high,low): 
# BlackOrWhite is a 0 or 1 depending on if the bar is present or not. A 1 indicates that you are below or equal to the true number. A 0 indicates that you are above the true number 

# the initial values for oldtrial, high, and low all equal yesterday's value 

factorIncrease = 4#5 
finished = 0 

if BlackOrWhite == 1 and oldtrial==high: 
    newtrial = oldtrial+factorIncrease*(high-low)+1 
    high = newtrial 
    low = oldtrial 
elif BlackOrWhite == 1 and high-oldtrial==1: 
    finished = 1 
    newtrial = oldtrial 
elif BlackOrWhite == 1: 
    newtrial = oldtrial+(high-oldtrial)/2 
    low = oldtrial 

if BlackOrWhite == 0 and oldtrial==low: 
    newtrial = (oldtrial)/2 
    high = oldtrial 
    low = newtrial 
elif BlackOrWhite == 0 and oldtrial-low==1: 
    finished = 1 
    newtrial = oldtrial-1 
elif BlackOrWhite == 0: 
    newtrial = oldtrial-(oldtrial-low+1)/2 
    high = oldtrial 

if (oldtrial==1) and low!=1: 
    finished = 1 

return finished,newtrial,high,low

来源

2012-12-08 Mark

问题是什么？如果你想要检查你的代码 - 请在[CodeReview.SE]（http://codereview.stackexchange.com/）上发布。如果你的算法失败 - 请提及它。其他，请直接说出它是什么 – amit

我的问题是，什么是最好的方式来找到我所说的边缘？任何指导表示赞赏（我的代码工作正常，但我不知道它是否是最有效的算法） – Mark

调用边缘确实可以通过修改的二进制搜索来完成。

与此问题类似：Find an element in an infinite length sorted array。

让搜索索引是idx

鉴于昨日的价值 - 你需要找到“边缘”，这样做可以随着找到/成倍减少IDX。

例如，如果昨天是1000，您将搜索1000,1001,1002,1004,1008,1016,1032,...直到您发现像素更改了开关的颜色。

假设您在迭代i中找到它，这意味着搜索的边缘在范围内的某处：[1000 + 2^(i-1), 1000 + 2^i]。（当然同样适用于向下而不是向上与[1000 - 2^(i-1), 1000 - 2^i]。

现在，你在这个范围内有一个经典的二进制搜索问题。

复杂性仍然O(logN)，其中N是从昨天起变化的高度。

来源

2012-12-08 22:39:49 amit

谢谢。这给了我一些想法。非常感激。 – Mark

边缘寻找二进制搜索

回答

相关问题