I think binary search is worth understanding, and I think you probably don't understand it, or don't understand it in the most helpful way. Here, let me fix that.
This is an elegant proof of the value of logarithmic approaches in real life, and not just abstract math examples. I'm not sure I've seen one quite so compelling before. Please let me know if you ever write about statistics for people who don't understand them at the mechanistic level, ha
RE stats: I might try at some point, but it's worth noting I'm not actually very good at stats! It's just that, as I've only quite recently realised, that the reason people side eye me when I say that is that what I mean by "I'm not good at stats" is "I am a bad statistician" and what most people mean when they say that is "oh god help"
nice read. I have a question, and sorry if it’s too pedantic, and possibly dumb; you say
> We don’t have a list, nothing is sorted, we’re not looking for a specific item.
isn’t the 8hr video a list of sorted frames?
a possibly contrived way to address the last part of quote would be that we could define our “target”, in claude’s words, as a subset of the search space that’s reasonably small to be searched via linear search, eg target = (the 5min clip where the theft happened)
Yeah, I think you can definitely reframe the video problem in a way that turns it into a series of discrete examples (e.g. frames does this automatically), but it's more natural to think of it as continuous, and there are places where you want to use binary search (e.g. root finding of a function, estimating some continuous quantity) which in some sense "really are" continuous and it's helpful to see how it works there.
Although note that the video is not automatically sorted in the relevant sense (as per the unstealing example), it's only sorted in time, but you want is for the frames to be sorted in order of "was the bike stolen?", which you (quite reasonably!) assume they are but can't actually verify in less than O(n) time, and you want the system to work without that verification.
Under a "no unstealing" assumption your five minute chunk solution does work as a way to turn it into a classical binary search though (where the sort order is by something like "number of endpoints of the chunk at which the bike is present"). I just think it's not especially informative to think of it this way, and it's better to think about the general principle.
This is an elegant proof of the value of logarithmic approaches in real life, and not just abstract math examples. I'm not sure I've seen one quite so compelling before. Please let me know if you ever write about statistics for people who don't understand them at the mechanistic level, ha
Thanks!
RE stats: I might try at some point, but it's worth noting I'm not actually very good at stats! It's just that, as I've only quite recently realised, that the reason people side eye me when I say that is that what I mean by "I'm not good at stats" is "I am a bad statistician" and what most people mean when they say that is "oh god help"
As someone in the oh god help category - or close enough to it - I suspect I'd still benefit from your writing on the subject!
It's not statistics, just probability, but you might find this thing I wrote on the notebook ages ago useful: https://notebook.drmaciver.com/posts/2021-10-29-09:43.html
What an amazing read, thanks for sharing. I will be thinking of this!
nice read. I have a question, and sorry if it’s too pedantic, and possibly dumb; you say
> We don’t have a list, nothing is sorted, we’re not looking for a specific item.
isn’t the 8hr video a list of sorted frames?
a possibly contrived way to address the last part of quote would be that we could define our “target”, in claude’s words, as a subset of the search space that’s reasonably small to be searched via linear search, eg target = (the 5min clip where the theft happened)
Yeah, I think you can definitely reframe the video problem in a way that turns it into a series of discrete examples (e.g. frames does this automatically), but it's more natural to think of it as continuous, and there are places where you want to use binary search (e.g. root finding of a function, estimating some continuous quantity) which in some sense "really are" continuous and it's helpful to see how it works there.
Although note that the video is not automatically sorted in the relevant sense (as per the unstealing example), it's only sorted in time, but you want is for the frames to be sorted in order of "was the bike stolen?", which you (quite reasonably!) assume they are but can't actually verify in less than O(n) time, and you want the system to work without that verification.
Under a "no unstealing" assumption your five minute chunk solution does work as a way to turn it into a classical binary search though (where the sort order is by something like "number of endpoints of the chunk at which the bike is present"). I just think it's not especially informative to think of it this way, and it's better to think about the general principle.