Comment on Binary search

<- View Parent
Ephera@lemmy.ml ⁨2⁩ ⁨weeks⁩ ago

Oh, well, you switch off half the fuses, then you go check the wire.
Let’s say the wire still has power on it, so now you know that none of the fuses in that half affected it (which you can turn back on now).

Then you do the same thing again with the other half of the fuses, i.e. you switch off half of the fuses in that half and go check the wire.
Now, let’s say the wire is dead, so now you know that the fuse you want is in this quarter.

So, then you flick off half of the fuses in that quarter and check the wire again, and so on.

With every step, you eliminate half of the remaining fuses, so for 60 fuses, you need at most 6 steps (which is the logarithm for base 2 of 60).

source
Sort:hotnewtop