Skip list gallop searchDue: February 23
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.