waves magic wand computer science!
Comment on Programmer tries to explain binary search to the police
Kalkaline@leminal.space 7 months ago
God damn, programmers are a clever group of people. I would have never come up with that on my own.
fsxylo@sh.itjust.works 7 months ago
jmcs@discuss.tchncs.de 7 months ago
What if you had to guess a number between 0 and 100 and the other person (or an application) only told you if the number is bigger or smaller? That’s the form that’s usually presented to CS students and most people end up figuring it out on their own. Then the trick is knowing how to generalize it.
systemglitch@lemmy.world 7 months ago
Honestly you probably do it already without thinking about it when trying to figure out where you left off a video that you never paused.
Or if you ever had VHS tapes, or so e from of disc media… perhaps a cassette when looking for a particular part of a song.
Maybe not as methodical as perfectly breaking it down into halves of halves, but xlos enough to help you pin point what part you are looking for.
Pamasich@kbin.social 7 months ago
I'm pretty sure they were using sarcasm.
Kalkaline@leminal.space 7 months ago
I’m pretty sure I was serious. I don’t know how people can be that clever. It seems simple once it’s explained, sure, but I wouldn’t be able to come up with that on my own without someone else giving me a problem that points me in that direction.
khannie@lemmy.world 7 months ago
Studied this in computer science algorithms class waaaaayyy back in 1996 and by golly this one stuck with me. It’s so simple and so effective.
CmdrShepard@lemmy.one 7 months ago
Works the same for finding a burned out bulb on a string of Christmas lights too.
acceptable_pumpkin@lemmy.world 7 months ago
Some security camera systems have this built in. They show snapshots of various times where you choose the total period, say 24 hours. Then you glance through the snapshots that are all displayed at once on the screen and click on the last one where you bike was still there. That will then “zoom in” the timeline and show another set of snapshots, though this time within a smaller total time window. Keep clicking on the last panel with the bike, and it will soon show you the clip of the bike being stolen.
Really helpful to find out when something changed.
dudinax@programming.dev 7 months ago
Yeah, there’s no reason it should take an hour no matter how long the tape is.
justJanne@startrek.website 7 months ago
If you’ve got 14 billion years, a theft takes a minute, then you need 53 recursion levels of binary search to find the moment of the theft.
That means OP assumed that it’d take 1 minute to decide whether at a certain still frame the theft had already occured or not, to compute the new offset to seek to, and the time it’d take to actually seek the tape to that point.
Not an unreasonable assumption, but a very conservative estimate. Assuming the footage is on an HDD and you’ve got an automated system for binary search, I’d actually assume it’d take 5 seconds for each step, meaning finding a 1min theft on 14 billion years of footage would take 5 minutes.
Anemia@lemmy.world 7 months ago
According to my napkin math it would take longer than an hour if the tape was ~3.3*10^218 sec long (or three million trillion trillion… (18 trillions) …trillion years). Assuming you have only have two options to choose between but can pick which alternative in in 5 seconds (2^720) and you want to get down to a 1 minute intervall.
So i mean its not impossible to find a tape long enough though it seems unlikely that we would be so off in our estimates of the age of the universe.
ODuffer@lemmy.world 7 months ago
Enhance…
SmoothLiquidation@lemmy.world 7 months ago
Uncrop.
ReplicantBatty@lemmy.one 7 months ago
Enhance!
Image
Cannacheques@slrpnk.net 7 months ago
Covert zorb ball carrying remote control toy racecar through the HRV system