二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现
如果数据存在在链表中，就不能使用二分查找了，若想需要使用二分查找，则需要对链表进行改造
为链表建立一级索引
如果我们现在要查找某个结点，比如 16。我们可以先在索引层遍历，当遍历到索引层中值为 13 的结点时，我们发现下一个结点是 17，那要查找的结点 16 肯定就在这两个结点之间。然后我们通过索引层结点的 down 指针，下降到原始链表这一层，继续遍历。这个时候，我们只需要再遍历 2 个结点，就可以找到值等于 16 的这个结点了。这样，原来如果要查找 16，需要遍历 10 个结点，现在只需要遍历 7 个结点。
加来一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了。那如果我们再加一级索引呢？效率会不会提升更多呢？
当数据量越大，建立的索引层级越多，查找效率的提升就会非常明显
这种链表加多级索引的结构，就是跳表
跳表可以让链表也能使用二分查找，但是需要额外的内存空间存储索引
若有收获，就点个赞吧
0 人点赞
