Fork me on GitHub
Math for the people, by the people.

User login

binary search

Keywords: 
lookup
Type of Math Object: 
Algorithm
Major Section: 
Reference

Mathematics Subject Classification

68P10 no label found16S40 no label found20G42 no label found16W35 no label found81R50 no label found16W30 no label found57T05 no label found54-01 no label found

Comments

Imagine that you are in a building with F floors (starting at floor 1, the lowest floor), and you have a large number of identical eggs, each in its own identical protective container. For each floor in the building, you want to know whether or not an egg dropped from that floor will break. If an egg breaks when dropped from floor i, then all eggs are guaranteed to break when dropped from any floor j ≥ i. Likewise, if an egg doesn't break when dropped from floor i, then all eggs are guaranteed to never break when dropped from any floor j ≤ i.

Define an algorithm with inputs(F, D, B) and output that determines whether or not an egg will break when dropped from any floor of a building with F floors, with the following restrictions: you may drop a maximum of D eggs (one at a time, from any floors of your choosing), and you may break a maximum of B eggs. You can assume you have at least D eggs in your possession.

Subscribe to Comments for "binary search"