Comment on Binary search
PM_Your_Nudes_Please@lemmy.world 2 weeks agoTurn off half the breakers. Now you know which half the outlet is on, based on whether or not it has power. Repeat.
For instance, let’s say you have 100 breakers. You turn off the first 50. Your target outlet still has power. So now you have divided the potential number of breakers by half, and you know the breaker is somewhere in 51-100.
So you cut that in half, and turn off 51-75. Your outlet is now dead, so you know it’s somewhere in the 51-75 range that you just turned off; if it were still on, it would be somewhere between 76-100.
So now you reset 51-63, while leaving 64-75 off. It is still dead, so you know it is somewhere between 64-75.
Maybe now you turn on all of the odd breakers, leaving the evens off. It is still dead, so you know it must be 64, 66, 68, 70, 72, or 74. Reset the first three. Your outlet has power now, so it must be one of the first three.
Flip 64 and 66 off. If you get lucky, your outlet still has power and you know it is 68. But you get unlucky, and it is dead. So now you know it must be either 64 or 66.
Flip 64 back on. If it has power, you know it’s 64. If it doesn’t, you know it’s 66.
We just eliminated 99 breakers and found the correct one using only 8 tests. Because each test eliminated half of the potential values, it whittles things down very quickly. We went from 1-100, to 51-100, to 51-75, to 64-75, to the evens between 64-74, to only 64/66/68, to 64/66, and finally landed on 66 as the correct breaker. If we had gotten lucky earlier, we could have done it in 7 instead. If you had simply started with breaker 1, it would have taken 66 trips to the breaker box to figure out.