My friend has some upcoming electrical work in his house, can you explain how to use binary search in this instance so I can tell him?
Comment on Binary search
Ephera@lemmy.ml 2 weeks ago
My dad once told me that he had to find the fuse that corresponded to a particular wire and because we have around 60 fuses in our house, he had to flick one off, run down and check the wire, run back up, flick the next fuse off, and do that quite a lot of times.
In that moment, I got to explain binary search to him and he was genuinely interested. 🙃
greenhorn@lemm.ee 2 weeks ago
spongebue@lemmy.world 2 weeks ago
Turn off half the breakers. See if you still have power where you need to go. That will tell you which half it’s on. Turn off half of those breakers, repeat.
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).
dan@upvote.au 2 weeks ago
Once you figure out which one it is, label it! I labeled all the breakers in my panel when I moved in to my house, as half of the existing labels were wrong (no idea why).
Fuckfuckmyfuckingass@lemmy.world 2 weeks ago
That’s the case with virtually every breaker box.
phughes@lemmy.ml 2 weeks ago
I keep a spreadsheet with every outlet/light in every room on it and their corresponding breakers. Much easier since breakers often span multiple rooms, sometimes only powering one or two fixtures in each.
greenhorn@lemm.ee 2 weeks ago
Ah, obvious now, thank you. For some reason
myhis brain couldn’t get to actually turning off half the breakers in one gointensely_human@lemm.ee 2 weeks ago
Binary search requires splitting the search space into two halves, then asking “is it in that half?”
Normally the “is it in that half?” check involves a numerical comparison: test value versus target value. “higher or lower” here gets you to “is it in that half?”
So finding the midpoint seems like a core part of the process, but really that’s just a shortcut in the case of comparable values, that helps you split into two and check membership.
I admit I couldn’t think of that either: just alter half the items and check for effect.
PM_Your_Nudes_Please@lemmy.world 2 weeks ago
Turn 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.
jol@discuss.tchncs.de 2 weeks ago
Binary search only works if the fuses were correctly sorted in the same order as the houses though.
domdanial@reddthat.com 2 weeks ago
I don’t think that’s true, it’s more of a set problem. If you pull half the fuses, and the thing is still one, then you’ve ruled out that half. Then you pull half the remaining fuses, and if it turns off it was one of the new half you pulled. Then you put another half back in, ect .
jol@discuss.tchncs.de 2 weeks ago
Ah, I didn’t think of it that way. That indeed would work.
Ephera@lemmy.ml 2 weeks ago
You know, after posting that comment, I really doubted myself, if it really is binary search, because Wikipedia also tells me it needs to be a sorted array.
But yeah, I think that’s only relevant, if your method of checking whether it’s in one half or the other uses
>and<. As far as I can tell, so long as you can individually identify the fuses, a.k.a. they’re countable, then you can apply binary search.lunarul@lemmy.world 2 weeks ago
If when you divide your set in two, you can reliably tell which of the two subsets definitely has what you’re looking for, then it’s binary search.
Anticorp@lemmy.world 2 weeks ago
If he can flick it off then it’s a circuit breaker, not a fuse. Fuses have to be pulled, and it’s a real PITA.
Ephera@lemmy.ml 2 weeks ago
Thanks, I changed it. I wasn’t sure, what the correct English word is…
Anticorp@lemmy.world 2 weeks ago
I would have never guessed that you’re not a native English speaker from your writing. Neat!
A fuse and a circuit breaker perform the same function, but a fuse blows out and has to be replaced, whereas a circuit breaker can just be flipped back on. Fuses haven’t been used in household wiring for a long time now, but they’re still used in cars, and for portable things like Christmas lights.
someguy3@lemmy.world 2 weeks ago
I think the old school method was to plug in a stereo and turn the volume up. When you couldn’t hear it then you got the right breaker.
phughes@lemmy.ml 2 weeks ago
I hook a cheap webcam up to a USB battery pack and load it up on my phone. Then I plug in a light and point the camera at that. It makes it a single trip and doesn’t bother the neighbors.