跳表是如何进行二分查找的？
除了二叉检索树，有序链表还有其他快速访问中间节点的改造方案吗？我们知道，链表之所以访问中间节点的效率低，就是因为每个节点只存储了下一个节点的指针，要沿着这个指针遍历每个后续节点才能到达中间节点。那如果我们在节点上增加一个指针，指向更远的节点，比如说跳过后一个节点，直接指向后面第二个节点，那么沿着这个指针遍历，是不是遍历速度就翻倍了呢？
同理，如果我们能增加更多的指针，提供不同步长的遍历能力，比如一次跳过 4 个节点，甚至一半的节点，那我们是不是就可以更快速地访问到中间节点了呢？
这当然是可以实现的。我们可以为链表的某些节点增加更多的指针。这些指针都指向不同距离的后续节点。这样一来，链表就具备了更高效的检索能力。这样的数据结构就是 跳表（Skip List）。
一个理想的跳表，就是从链表头开始，用多个不同的步长，每隔 2^n 个节点做一次直接链接（n 取值为 0，1，2……）。跳表中的每个节点都拥有多个不同步长的指针，我们可以在每个节点里，用一个数组 next 来记录这些指针。next 数组的大小就是这个节点的层数，next[0]就是第 0 层的步长为 1 的指针，next[1]就是第 1 层的步长为 2 的指针，next[2]就是第 2 层的步长为 4 的指针，依此类推。你会发现，不同步长的指针，在链表中的分布是非常均匀的，这使得整个链表具有非常平衡的检索结构。
a7a1asa6a8a9a4a2a3
理想的跳表
举个例子，当我们要检索 k=a6 时，从第一个节点 a1 开始，用最大步长的指针开始遍历，直接就可以访问到中间节点 a5。但是，如果沿着这个最大步长指针继续访问下去，下一个节点是大于 k 的 a9，这说明 k 在 a5 和 a9 之间。那么，我们就在 a5 和 a9 之间，用小一个级别的步长继续查询。这时候，a5的下一个元素是 a7，a7 依然大于 k 的值，因此，我们会继续在 a5 和 a7 之间，用再小一个级别的步长查找，这样就找到 a6 了。这个过程其实就是二分查找。时间代价是 O(log n)。
跳表的检索空间平衡方案
不知道你有没有注意到，我在前面强调了一个词，那就是 「理想的跳表」。为什么要叫它「理想」的跳表呢？难道在实际情况下，跳表不是这样实现的吗？的确不是。当我们要在跳表中插入元素时，节点之间的间隔距离就被改变了。如果要保证理想链表的每隔 2^n 个节点做一次链接的特性，我们就需要重新修改许多节点的后续指针，这会带来很大的开销。
所以，在实际情况下，我们会在检索性能和修改指针代价之间做一个权衡。为了保证检索性能，我们不需要保证跳表是一个理想的平衡状态，只需要保证它在大概率上是平衡的就可以了。因此，当新节点插入时，我们不去修改已有的全部指针，而是仅针对新加入的节点为它建立相应的各级别的跳表指针。具体的操作过程，我们一起来看看。
首先，我们需要确认新加入的节点需要具有几层的指针。我们通过随机函数来生成层数，比如说，我们可以写一个函数 RandomLevel() ，以 (1/2)^n 的概率决定是否生成第 n 层。这样，通过简单的随机生成指针层数的方式，我们就可以保证指针的分布，在大概率上是平衡的。
在确认了新节点的层数 n 以后，接下来，我们需要将新节点和前后的节点连接起来，也就是为每一层的指针建立前后连接关系。其实每一层的指针链接，你都可以看作是一个独立的单链表的修改，因此我们只需要用单链表插入节点的方式完成指针连接即可。
这么说，可能你理解起来不是很直观，接下来，我通过一个具体的例子进一步给你解释一下。
