In terms of physical effort taken it’s O(n). Move half, then a quarter, then one eighth, etc.

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.

It's O(logn) but you haven't accounted for how heavy each item in the array of n is.

Or you could use a very heavy blanked to just cover some boxes to supress the sound enough to simulate moving boxes.

You are moving n/2 objects log(n) times, so its O(n.log(n))

Never ignore the constant factor.

That was my proposed solution to finding something just today; it didn’t work, but one of the bags ended up containing an old contract from General Development Company. Apparently a late family member had been buying some land down there through them, but county appraisers showed that the land never changed hands until after GDC’s bankruptcy. Not even their kid had heard about this, so it really makes me wonder what the story was behind that considering they lived in the Midwest (but did have some relatives nearby in Florida).

Yes, but that's also O(log n) physical effort. This one's O(1) sitting on your butt.

(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).

You just look in the last box first, duh.

That requires you to stand in the room and listen for which side. So it’s nlogn times a very long time constant

> Move half the boxes to another room.

Alternatively, no.

You could also solve it by getting rid of the boxes of stuff you clearly don't need (if you needed it, it wouldn't still be in a box). The best way to solve a problem is to make the problem go away.