Does the solution have to be deterministic? If an adversary places the hotel after looking at my algorithm, my first inclination is introduce uncertainty into my search.
No. But you can't do better than O(k) anyways, and you can do O(k) deterministically.
Related to: Half-assing it with everything you've got; Wasted motion; Say it Loud.
Once upon a time (true story), I was on my way to a hotel in a new city. I knew the hotel was many miles down this long, branchless road. So I drove for a long while.
After a while, I began to worry I had passed the hotel.
So, instead of proceeding at 60 miles per hour the way I had been, I continued in the same direction for several more minutes at 30 miles per hour, wondering if I should keep going or turn around.