邊緣尋找二進制搜索

想象一下，使用條形圖每天僅以圖形形式發佈每日通勤者人數的網站。我想通過在將圖形保存爲圖像後讀取條形圖來確定數字（圖像內容在此不重要）。我想要讀取條形圖的方法是通過尋找一個像素號（＃號通勤者軸）並提出問題：「像素是在」還是「關閉」？（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

邊緣尋找二進制搜索

回答

相關問題