this post was submitted on 02 Dec 2024
1491 points (99.3% liked)
Memes
8516 readers
335 users here now
Post memes here.
A meme is an idea, behavior, or style that spreads by means of imitation from person to person within a culture and often carries symbolic meaning representing a particular phenomenon or theme.
An Internet meme or meme, is a cultural item that is spread via the Internet, often through social media platforms. The name is by the concept of memes proposed by Richard Dawkins in 1972. Internet memes can take various forms, such as images, videos, GIFs, and various other viral sensations.
- Wait at least 2 months before reposting
- No explicitly political content (about political figures, political events, elections and so on), [email protected] can be better place for that
- Use NSFW marking accordingly
Laittakaa meemejä tänne.
- Odota ainakin 2 kuukautta ennen meemin postaamista uudelleen
- Ei selkeän poliittista sisältöä (poliitikoista, poliittisista tapahtumista, vaaleista jne) parempi paikka esim. [email protected]
- Merkitse K18-sisältö tarpeen mukaan
founded 2 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
My dad once told me that he had to find the circuit breaker that corresponded to a particular wire and because we have around 60 circuit breakers in our house, he had to flick one off, run down and check the wire, run back up, flick the next circuit breaker 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. 🙃
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. 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 7 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 6 instead. If you had simply started with breaker 1 and worked subsequently, 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 three or four searches (1-1000 > 1-500 > 1-250 > 1-125 > 1-75… etc…) to narrow it down.