alt Hacker NewsYes, 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).
Replies
MisterMunchkin • today at 6:15 AM
It’s not sitting on your butt if you have to code an entire system and set up notes throughout the house and monitor them.
Good point about the moving effort required. But if moving an object takes constant time, then it's O(n) overall -- since <incorrect argument deleted>.
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.