That still seems like a lot of work. If I understand correctly, you’re basically doing the same thing you described in the first sentence, but you’re doing it using bisection, instead of doing it linearly (much faster, but still not O(1)).
As I mentioned in the question, your vehicle should have a member variable that holds the number of the last spline point it reached. Then, you can just compare two points at a time, not N (all) of them.
I’ll write an answer with more details.