This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
We know from class that searching for an item in a skip list takes expected \(O(\log n)\) time. But what if the item we are searching for is known to be near the beginning of the skip list?
Define k as the index of whatever we are search for in the skip list. So for example if we're search for the 2nd smallest thing in the skip list, \(k=2\). Devise a simple algorithm to search for the kth smallest thing in a skip list that has expected running time \(O(\log k)\). Describe your algorithm in pseudocode and with a well-chosen example to show how it works.