I have a collection of numbers. After each update, one number from the collection is removed and another number is added. After each update, I want to know the upper and lower bounds that best encloses the numbers in the collection with the constraint that the distance between the upper and lower bounds is always a fixed width and never changes. The maximum width of the enclosing bound will be a parameter to the algorithm. Further, I know that the domain of all numbers observed will always fall within some other wider fixed lower (DL) and upper bound (DU). So the problem can be solved by simply setting the lower bound == DL and upper bound == DL + width of enclosing bounds, computing the number of points inside the bounds and comparing against all other positions until the upper bounds == DU, then select the position that encloses the most points. However, is there a more efficient algorithm to do this that takes advantage of the fact that the state only changes by 1 element between each update?
Background / Motivation: The purpose of this algorithm is to implement an adaptive binary search. Depending on observed data, it may be possible to adaptively reduce the search range of a binary search in order to complete the search in fewer steps.
For example, say I want to program an automated wafer tester to characterize the minimum voltage with which a part can pass a given test. Assume that the part will consistently fail at all voltages below a threshold voltage and pass at all voltages above that threshold voltage. In that case, I can use a binary search to find that threshold voltage. It might also be the case that although I am required to search across a wide range of voltages, say 1.0V to 2V, I might find that on a large sample of thresholds collected during testing, that most of the data falls within the range of 1.0V to 1.5V and rarely falls outside that range. Then in that case, I can reduce my search range to 1.0V to 1.5V with the condition that if it fails at 1.5V, then I'll need to repeat the search across 1.5V to 2.0V to cover the full range. In that case, when I guess wrong, I end up having to effectively do the search twice. However, if I am right that the real data falls within 1.0V to 1.5V most of the time, then by being able to cut my effective search range in half for most cases, I can save one iteration of the binary search and reduce the overall cost of performing the test.
I tried to keep the problem description as general and concise as possible above, but that's what I am trying to do. Given a full search range defined by DL and DU, I would like to know the most likely continuous subrange of that full range that is exactly half the width of the full range based on the last N observed points. I would then look at what percentage of those past N datapoints actually fall within that range to estimate the likelihood of making a correct guess to determine if I should use the subrange or not (as in some cases, the data may span most of the full range and this strategy could backfire). Key point: I'm only interested in subranges that are an exact power of 2 smaller than the full range (0.5, 0.25, 0.125, etc). Reason being is that if I am able to reduce my search range by only 40%, that will not allow me to reduce the number of steps in my binary search. I can only save a step when I can cut the search range by half or more.