1) Move half the boxes to another room.
2) Listen for a beep and determine which room the beep comes from.
3) Take the boxes in that room and split them in half again.
4) Repeat until one box is left.
The number of partitions doesn’t matter either, the most straightforward case is the beeping box always being in the original room, so regardless of strategy you move n-1 boxes to narrow it down, and by symmetry it doesn’t matter which room beeps.
I also feel like ordering the moves by lightest box first is reasonable as a real-world optimization.
- the boxes are stacked
- the heavy boxes are at the bottom of a stack, and you can't stack a heavy box on top of a light one
- boxes aren't the same size
- some boxes are open, so must be put on top
- storage space and height are limited(Out of curiosity: I think "physical binary search" is more properly O(n^{1/3} log(n)), or maybe O(n^{1/2} log(n)). Since physical objects have sizes, and moving things (or moving between things) takes time proportional to distance).
EDIT: My earlier analysis was wrong (it assumed you never move the beeping item after the initial halving), but the conclusion was right for a different reason: Each time you move items, you move half as many as you did last time. You initially move n/2 items, and the geometric series n/2 + n/4 + n/8 + ... + 1 sums to n-1. So O(n) moves are done, and this dominates the log n term for the number of steps.
O(log n) is if you can split the collection in half in an O(1) step, like, *shoving* the whole pile together as a unit
O(n) if you're moving items one at a time. So, splitting the pile in half once is O(n)
O(n^{3/2}) if the project is way out of control and walking distances start to matter
Alternatively, no.
I like to keep a lot of things in storage, and sometimes go through my boxes and “rediscover” things I haven’t used in a while.
Sure I have a lot of things I never use also. Some things I could sell, and some things I could give away, and some things I could throw away.
But just because a lot of things are in boxes, doesn’t mean that I might as well get rid of all of it for that reason alone.
And the piles of rubbish at the landfill are probably beeping too.