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.
- 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 limitedI also feel like ordering the moves by lightest box first is reasonable as a real-world optimization.
(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.