Skip lists with limited height
Hint: If the height is $k$, then the search complexity should be $O(kn^{1/k})$ (so the best choice is $k = \log n$, giving logarithmic time). Each level should contain every $n^{1/k}$th element of the lower level. Do the obvious thing - find the two elements bracketing your element in the first level, then the two elements bracketing it in the second level, and so on.