Imagine a website that publishes the number of daily commuters in only a graphical form each day using a bar chart. I want to determine the number by reading the bar chart after saving the graphic as an image (the image stuff is not important here). The way I want to read the bar chart is by going to a pixel number (the #of commuters axis) and asking the question, "Is the pixel 'on' or 'off'?" (On means that the bar is present and off means that this guess too high) Note: that there is a lower bound of 0 and, technically, an infinite upper bound. But, in reality, 10000 may be the realistic upper bound. Also note, No Change from yesterday is a frequent finding.
Given a starting number from yesterday to guess, what's the most efficient way to find the number? Does my function provide the most efficient method? Efficient means fewest number of queries to ask if a pixel is on or off. There will be multiple bars to measure and keeping track of the iteration number might add unwanted complexity if it's not truly needed.
My algorithm follows as a function. Any advice is most welcome. (brought to CR from SE, http://stackoverflow.com/questions/13782587/edge-finding-binary-search )
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