algorithm - 寻边 二分搜索

Question

假设一个网站每天使用条形图以图形形式发布每日通勤者的数量。我想在将图形保存为图像后通过读取条形图来确定数字(图像的东西在这里并不重要)。我想阅读条形图的方式是转到一个像素编号(#of commuters 轴)并询问“像素是‘开’还是‘关’？” (打开表示条形存在，关闭表示此猜测太高)注意:下限为 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

Answer 1

确实可以通过修改后的二分查找来调用边。

类似于这个问题:Find an element in an infinite length sorted array .

设搜索索引为idx

鉴于昨天的值(value) - 您需要找到“边缘”，这样做可以通过以指数方式增加/减少 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 是自昨天以来变化的高度。