Optimizing Number Isolation: Equal vs. Unequal Bisection Strategies

[Loren Booda]

Given a large but finite number line including an arbitrarily chosen number, what strategy of (un)equal bisections will isolate that number within a minimum of steps? For instance, should one choose equal bisecting, or would a series of unequal 2:1 bisecting be more efficient? Might e or phi be involved?

 

[Dragonfall]

What do you mean by isolate?

 

[NateTG]

Binary search is the fastest if you split into halves don't care about the results.

There's a puzzle (with, I'm told, applications in networking) where you've got two (or some number of eggs) and 100 (or some number) of floors, and you want to find out what the highest you can drop the egg from without breaking it as quickly as possible. Since only a small number of negative results is acceptable more exotic search strategies are preferred.

 

[Loren Booda]

Dragonfall,

By isolate I mean eventually creating a section within which only a given number resides.

 

[NateTG]

By isolate I mean eventually creating a section within which only a given number resides.

If you have a probability distribution, then you'll want to bisect the probability, and not the range.

For example, if the probability that the number is n is \frac{1}{2^n}, then you'd be splitting between 1 and 2, then 2 and 3, then 3 and 4, and so on.

 

[Loren Booda]

I believe you're quite right, Nate.