It may be noted that in level 1, links point to every second element in the list. In level 2, the links point to
every fourth element in the list. Thus, it can be deduced that a link in the ith level will point to 2*ith element
in the list. A point worth noting is that the last node of the skip list is pointed by links of all levels.
Now the search within the skip list shall take O(log n) time as it will follow binary search pattern.
For example, the search for ‘53’ will follow the route shown in Figure 10.27.
The algorithm that searches a value VAL in the skip list is given below:
Algorithm
skipListSearch ()
{
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month, and much more.