Hacker News new | past | comments | ask | show | jobs | submit
aizk | on: Locating the source of a mysterious beep
It's O(logn) but you haven't accounted for how heavy each item in the array of n is.
StilesCrisis | parent | next
You can just move the lightest half of the boxes each time.
loading story #50441681
kelseyfrog | parent | next
If you randomly index them and there's enough of them then on average the partitions average out.
mauvehaus | parent | next
This is true, but it probably isn't a box of books that's beeping.

I also feel like ordering the moves by lightest box first is reasonable as a real-world optimization.

Spare_account | root | parent
Typically, the heavy boxes are at the bottom too; to some extent, the piles will already be sorted by weight.
tonyarkles | parent
Lol classic “ignore the constant factor” gotcha when using Big-O.