If it’s not “for the duration of the rest of the video,” then binary search would be useless
That’s not true. It only has to be long enough to be detectable, by landing on a strip of video that it exists on. It’ll be harder, definately, but still doable.