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. 🙃
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.
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.
Binary search only works if the fuses were correctly sorted in the same order as the houses though.
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.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.
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 on, 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 .
Ah, I didn’t think of it that way. That indeed would work.
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.
Thanks, I changed it. I wasn’t sure, what the correct English word is…
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.
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?
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.
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).
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).
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.
That’s the case with virtually every breaker box.
Why are so many mislabeled though? It’s not like the loads are being changed every day. I had two breakers labeled “dishwasher” and neither of them were the dishwasher!
I had two breakers labeled “dishwasher”
Electrical work is one of those things that’s not difficult to do as long as you don’t mind it being some level of wrong but relatively hard to do 100% to code right without training. With most of the wrong ways, the project still works, but it’s dangerous and/or hard to maintain. Professional work is expensive, so you end up with a LOT of handyman work that’s poorly labeled, poorly run, poorly designed or some combination of the three.
My best guess would be that at some point, running the dishwasher tripped the breaker. They had space so they added a breaker below it and moved the line to the new breaker. Then it still tripped, so they moved the line at the dishwasher circuit that was already close by.
Either the original line has a fault in it (old aluminum lines can have junction issues over time) or the dishwasher had a short in it, and they either replaced the dishwasher, or the new line they chose didn’t fail.
Ah, obvious now, thank you. For some reason
myhis brain couldn’t get to actually turning off half the breakers in one goBinary 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.
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.
Where binary search really excels is with large data sets. Even if it had been 1000 breakers instead of 100, it still would have only taken an extra two or three searches to narrow it down.
When I read this originally, it was a nice example how programmer brain can be applied IRL. Also works when trying to find something and I see the listing is someway sorted, like time tables and eshop product categories.
I remember marveling at how simple and obvious binary search was when I first learned about it in programming.
The cops don’t like when you point out how intelligent they are (or aren’t really)?
I am shocked
/s
Expecting feral hogs to be capable of reason was a mistake.
git bisectHe was never interested in finding the bike, he just wanted to “take notes” and go back to his donuts.
Honestly, this was the comment that exposed me (regular office rube) to binary search as a concept and it is so. fucking. helpful.
In what ways do you use it in your daily life? Genuinely curious.
not the commenter you asked but i use a binary search when i’m playing a modded game that is having issues to pinpoint which mod(s) cause the issue. beats launching the game over and over to test each mod by a long shot.
a recent example: i put together a mod list for risk of rain 2 to play with some friends, but the game crashed on launch when all the mods were installed. so i disabled half the mods (in order, alphabetically or other) and tried to launch the game again - still crashing. disabled half the remaining enabled mods, test, repeated as necessary. with only a few cycles of booting the game, i was able to determine the specific mod causing a crash on startup out of my list of 50 something mods.
While that’s really cool and useful, it might be the way a couple of mods interact as opposed to a specific one.
Sure, but it’ll still narrow down on one of those mods - perfect information would require figuring out why it crashes in the first place, but finding at least one of them would let you play the game without it and look up if anybody else reported problems with that mod.
Imagine you work at a company that sells cookies. The company offers a variety of cookies at different price points to different customers. They set up contracts saying they will offer a customer a set variety of cookies at various prices, with a clause stating that if the customer wants a different type of cookie the company makes later on, it will be priced and added to their list. This should be in the form of regular contract amendments/addendums, but it isn’t.
Several years go by, and in the course of that several different varieties of cookies have been added by the customer. The price given to them at the time may not account for the cost of materials and labor today, or how many of those cookies not mentioned in the contract are being ordered v. how many were expected, the fact that you outsourced some of those cookies, or brought some of those cookies in-house, etc. The cookie executive asks you “When did we offer customer x cookie y at price point z?”
Now, the company has a perfectly good database of cookies and price points for customers, but it’s very old tech and requires certain access privileges, which are very hard to give people outside of the accounting department. Accounting is never able to help with this, and the cookie executives try poorly and fail to get people like you access. But you do have years and years of cookie addition request forms, which are kept in chronological order by customer and contain a list of all types of cookies requested up to that point in time.This is where binary search helps - you can pretty quickly find the one where the cookie y was added even though there are hundreds of these forms.
It’s not a situation that should exist - we have a god damn cookie database where you can just pop in customer x and cookie y to get price z, with an effective date - but in my crazy cookie factory it helps a ton.
There’s other examples but they’re all pretty much variants of this thinly veiled analogy.
That doesn’t make sense at all. How would you - given two stacks of papers - know which stack the correct form is?
There’s lots of stuff about what I do that doesn’t make much sense :)
It works in this scenario because the stacks are reliably sorted by customer and date, and each form has a running tally of what cookies are on offer as things get added to the list.
Assume customer x’s forms are taken out, and you make two stacks of them without shuffling the forms. The very first form on the first stack from 2022-01-01 does not include cookie y. The first form on the second stack, from 2023-02-01, also does not contain cookie y. Based on this information and the conditions above, you can infer that the form you want is in the second stack.
Now, if the forms were not reliably sorted, or did not contain a running record, you’d need to approach this differently. Strategies would probably involve inferences or straight getting the info you need from other sources - custumer correspondence around “We want cookie y, how much?” (if it occurred when you were in a position to get such correspondence); knowledge of big changes to cookie offerings to the customer (contract renewals); bugging accounting at a regular, annoying cadence with progressive escalation until they answer/complain about you bugging them, etc.
Sometimes that’s just the way the cookie crumbles, man
It’s a crummy job, but someone’s gotta do it.
Slightly irked you didn’t spell it “crumby” 😅
There’s a similar logic applied to fault finding, start at the middle of the circuit.
If the fault is before that point, start at the quarter point, if it’s after, three quarters, and keep splitting until you find it.
Not just similar, it’s the exact same thing.
Man, as someone who worked surveillance for years, I can’t believe that anyone would have a hard time with this.
It was so, so, so, so easy to find when something vanished.
Now, did so and so walk in the building? Yeah, kiss my ass. Not happening.
I worked at a major outdoors retailer with a “gun library” of high-end firearms.
In one of our quarterly steel audits (where we pull all 10,000 guns put hands on them, verify the serials, etc) we discovered a $10,000 rifle was missing.
The thing is, the case it was in obscured the gun itself from the security cameras. It was behind like 6 other guns in a glass case any customer could item and pull the guns out to look at them (guns themselves were trigger-locked of course).
So we had to have the gun library manager sit there and watch 3 month’s of surveillance video of a specific case that was proclaimed opened 20 times an hour in a highly-trafficked area of the store. Because of all the activity, the video had to be watched in real time, and we were open 13 hours a day.
The manager ended up quitting over the boredom combined with stress.
Did they ever find the gun?
No.
Honestly, if your security system didn’t allow you to set motion alerts, that’s a bad system. Basically any modern system will allow you to set motion alerts. You can specify a section (or sections) of the screen that will create a flag in the footage when motion is detected.
My job’s parking garage had a car get broken into, and a musician’s (very expensive) instrument was stolen. We didn’t have a camera pointed directly at the car that was broken into, but we had cameras at every entrance and exit, and on the ramps leading between each floor. Management was expecting to scrub through literal hours of footage. Using some basic motion detection, I set it to flag any time someone came up or went down the specific ramps or stairs that led to the level the car was on. It ended up being like 45 cars.
Then I just did a quick timer, to see how long each person lingered on the floor. Like 40 of the cars came up the ramp from the lower level, then like 30 seconds later went up the next ramp to the next level. So it wasn’t them. Only like five of the cars actually didn’t go to the next level.
And out of those five cars, four had drivers/passengers seen on the stairwells leading back down to the ground floor; They had parked on the same level as the incident, and went downstairs.
Only one car lingered on the same level for about 2 minutes, then quickly left again. At the exit, there was a camera on the gate which pointed into the cars. We got crystal clear footage of the driver, (someone who the musician knew) and the instrument case was very obviously sitting in the passenger seat.
The entire search (it was like 3 days of footage) took like 10 minutes total, simply by being able to whittle down when people were coming and going.
It was a high-tragfic area of a retail store. Motion alert is useless.
I can’t imagine having someone watch 3 months x 13 hours of real-time security footage is worth the 10k, unless the insurance would pay his salary.
But now I know why stores sometimes have their most expensive stuff just sitting there in full view. It’s not just for the customers’ viewing.
Yeah it’s a sunk cost fallacy. 91 days x 13 hours = 1,183 hours. Even assuming the manager is making $10 an hour they wouldn’t recoup the loss unless they found it early.
Ofc no manager makes $10/hour.
Let’s make some assumptions. just picking a retail place with firearms managers and i see cabela’s listed on glassdoor reporting $53-91k. Let’s go with the low end 53k. Let’s also assume 40 hours per week and the manager is doing no more than 20% unpaid hours, so 2080 salary hours + 208 “good worker” hours = 2288 total hours worked in a year. 53k salary / 2288 hours = $23/hour effective pay rate. That’s even before considering the benefits package
$10,000 item / $23 per hour = ~435 hours of real time footage before it is a guaranteed sunk cost. This means finding it within first ~37% of footage. Meanwhile 435 hours would effectively take the manager off the floor for a quarter of the year.
I didn’t need to do math to tell you that this is a task given to someone to make them quit. Manager did something else and this how the company decided to get rid of them.
Oh god, yeah I’d be out. I would not do that.
Watching surveillance is truly like watching paint dry. Realtime? Yeah, just shoot me.
The only time I ever struggled was when cash went missing and I had to watch sale for sale. Even then, I could fast forward.
I always went for voids and “nosales” first. Nine times out of ten that’s where I’d find the theft. More clever thieves made my life hell though.
Aaaaaaagh, why cant you talk this way to people?! Life would be so much easier! Why didnt the argument go down well?! Is the cop stupid?! Binary search works! The guy was correct! God damnit, why must people be so unaccommodating, even when proven their accommodation would not take long?
My bike was stolen, and I live in a small enough town that the cops actually did go through the footage to find the thief.
He called back 15 minutes later for more details and mentioned he was 15 minutes into the footage.
It sounds dumb, but if the footage was on tape and not easily seekable, then I can see that happening.
It should still at least have a fast-forward option. You go at the highest speed possible until the bike disappears. Then you rewind at a slower speed until it shows up again. Then you can play the tape from there.
lol
Drag has been in exactly this same situation. Stupid pigs.
Also binary search isn’t a sorting algorithm. It’s a search algorithm. It only works on a data set that has already been sorted.
Could you not say that the data set has already been sorted by time?
Drag is implying that. You could also say that the frames are sorted by bike present and not. Assuming the bike isn’t returned before the end of the tape.
Thank you.
