二分查找底层依赖的是数组随机访问的特性。只能用数组来实现。
跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作。（类似于链表的二分查找实现）
理解跳表
对于一个单链表来讲，即使链表中存储的数据是有序的，如果想在其中查找某个数据，也只能从头到尾遍历链表。查找效率低，时间复杂度高，O(n)。
对链表建立一级“索引”，提高查找效率。每两个结点提取一个结点到上一级，把抽出来的那一级叫作索引或索引层，down指针指向下一级结点。
查找某个结点时，可以先在索引层遍历，当遍历到索引层中目标结点附近，通过索引层结点的down指针，下降到原始链表这一层，继续遍历，找到目标值的结点。
加一层索引之后，查找一个结点需要遍历的结点个数减少了，查找次数减少了、效率提高了。
类似的，可以在第一级索引的基础之上，每两个结点就抽出一个结点到第二级索引，查询效率进一步提升。
链表加多级索引的结构，就是跳表。
跳表查询时间
查询数据的时间复杂度推算：
每两个结点抽出一个结点作为上一级索引的结点，第一级索引的结点个数大约为n/2，第二级索引的结点个数大约为n/4，第三极结点个数大约为n/8，以此类推，第k级索引的结点个数是第k-1级索引的结点个数的1/2，第k级索引结点的个数就是n/(2k)。
假设索引有h级，最高级的索引有2个结点。通过公式，可以得到n/(2h)=2，求得h=log2n-1。如果包含原始链表这一层，整个跳表的高度就是log2n。
在跳表中查询某个数据的时候，如果每一层都要遍历m个结点，那么在跳表中查询一个数据的时间复杂度为O(m*logn)。
每一级索引最多只需要遍历m个结点，在跳表中查询任意数据的时间复杂度是O(logn)。与二分查找的时间复杂度相同，等同于基于单链表实现了二分查找。
跳表空间占用
比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。
假设原始链表大小为n，每2个结点抽一个作为上一级索引的结点。每上升一级索引，结点个数就减少一半，知道剩下2个结点。每层索引的结点数就是一个等比数列，索引结点总和就是n/2+n/4+n/8+…+4+2=n-1。所以跳表的空间复杂度为O(n)。
如果将包含n个结点的单链表构造成跳表，需要额外再用接近n个结点的存储空间。
每三个结点抽一个，总的索引结点大约是n/3+n/9+n/27+…+9+3+1=n/2。类推可以减少索引节点存储空间。
实际开发中，原始链表中存储的可能是很大的对象，索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，索引所占用的额外空间可以忽略。
跳表插入和删除
跳表插入、删除操作的时间复杂度为O(logn)。
在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的为O(1)。但为了保证原始链表中数据的有序性，需要先查找到要插入的位置，这个查找操作比较耗时。
对于纯粹的单链表，需要遍历每个节点来查找到插入的位置。但是对于跳表来说，查找到某个结点的时间复杂度为O(logn)，查找到某个数据应该插入的位置的时间复杂度就为O(logn)。
删除操作，如果要删除的结点在索引中也有出现，除了要删除原始链表中的结点，还要删除索引中的。
单链表中的删除操作需要拿到要删除结点的前驱节点，然后通过指针操作完成删除，在查找要删除的结点的时候，要获取前驱节点。双向链表不需要。
跳表索引动态更新
当不停的往跳表中插入数据时，如果不更新索引，有可能出现某2个索引结点之间数据非常多的情况。极端情况下，跳表会退化成单链表。
跳表通过随机函数来维护平衡性。
往跳表中插入数据的时候，可以选择同时将数据插入到部分索引层中。
如随机函数生成了值K，就将这个结点添加到第一级到第K级这K级索引中。
跳表与红黑树对比
插入、删除、查找、迭代输出有序序列的操作，跳表与红黑树的时间复杂度相同。
按照区间查找数据操作，红黑树的效率没有跳表高。跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以，非常高效。
红黑树在编程语言中一般有现成的实现；跳表没有，需要自己实现再使用。