You can use finger search algorithm. It has the required running time, since it starts and ends at two nodes at the deepest level of a skip list. A variant of this algorithm is described and available in the article
Efficient Representation of a Semigroup in C++[
^], see Figure 1 for its illustration.
In general, note that level-linked B+ trees are better choice than skip lists, since they are deterministic data structures. In addition to this, I suggest measuring performance of both algorithms (top-down and finger search), if you are planning to use them in practical applications.
Regards,
Vadim Stadnik