An algorithm for making 2 carts meet
You asked for a hint.  OK, here goes:

Obviously, we don't know $D$ (otherwise the problem is too easy).  But suppose we do know an upper bound $U$ on $D$.  In other words, suppose we know an integer $U$ and are promised that $D \le U$.  Then it is possible to build a solution whose running time is a low-order polynomial of $U$.  In fact, it is possible to build a solution whose running time is $O(U^2)$.  Take a close look at your professor's algorithm (the one labelled "the given algorithm"), and think for a bit, and maybe you'll see how to accomplish this.

But what about the fact that we don't know the value of $U$?  Well, you might ponder the sequence $1,2,4,8,16,32,\dots$.  I'm being deliberately terse here since you asked for a hint, but if you ponder on this, I think you'll be able to find an algorithm that it meets all your criteria.