Alternatively, no.
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(Solely for entertainment purposes: I think "physical binary search" is more properly O(n^{1/3} log(n)), or maybe O(n^{1/2} log(n)). Because real objects have sizes, and moving things (or moving between things) takes time proportional to distance).
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 is O(n)
O(n^{3/2}) if the project is growing out of control and walking distances start to matter
O(n^{4/3}) if that, but somehow it's taking place in 3-dimensions
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.
n. Sum(2^-i)=n
So its o(n. Log(n))
sum_{i=1}^{log_2(n)} {(n/2^i)} = n - 1
So it's O(n).
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'll see myself out...
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 it in half again.
4) Repeat until one box is left.