Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Isolation by bisection

  1. Jun 29, 2006 #1
    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?
  2. jcsd
  3. Jun 30, 2006 #2
    What do you mean by isolate?
  4. Jun 30, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    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.
  5. Jun 30, 2006 #4

    By isolate I mean eventually creating a section within which only a given number resides.
  6. Jun 30, 2006 #5


    User Avatar
    Science Advisor
    Homework Helper

    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 [itex]n[/itex] is [itex]\frac{1}{2^n}[/itex], then you'd be splitting between 1 and 2, then 2 and 3, then 3 and 4, and so on.
  7. Jun 30, 2006 #6
    I believe you're quite right, Nate.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Isolation by bisection