聊聊二分查找与跳表

二分查找也称折半查找, 是一种效率较高的查找方法,但是使用的条件比较苛刻。下面以一个猜数字游戏为例学习二分查找的过程。

游戏的规则:1到10的数字中, A选一个数字,B去猜,B猜数字的时候,A会回答小啦、大啦或者猜对啦, B怎么做才能在最少次数里猜对呢。

用二分查找法,B最多需要4次即可猜对啦,下面用个图来展示一下过程:

binary_search

B每次猜的时候是取中间的数字,总数为偶数个时,中间数会有两个; 总数为奇数个时,中间数就只有1个。代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//下面代码是用递归方式来实现, 也可以用非递归方式来实现
private static int binarySearch(int[] arr, int start, int end, int key){
if(arr == null){
throw new IllegalArgumentException("传入的数组不能为null!");
}
if(start < 0 || end < 0 || start > end){
return -1;
}
int middle = (start + end) / 2;
int temp = key - arr[middle];
if(temp == 0){
return middle;
}else if(temp > 0){
return binarySearch(arr, middle + 1, end, key);
}else {
return binarySearch(arr, start, middle - 1, key);
}
}

public static void main(String[] args){
int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int index = binarySearch(data, 0, data.length - 1, 1);
System.out.println("index: " + index);
}

也许数量少,才10个数,可能有种错觉,查找也不是很快啊,每次折半,数量级是2幂次方,2的32次方已经是亿级别了,查找一个数也就需要32次。 二分查找使用时,必须是一个有序数组, 依靠数组index折半才能实现高效, 而且实现开发中,通常使用是对象,也会有相等的元素出现,所以实现开发中还是要看情况使用二分查找法。

跳表

跳表的原理类似二分查找,但是数据结构用得链表,跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。理论有点抽象,下面也用个图来说明一下:

skip_list

上图例子中是使用了一个单链表实现的简单的跳表, Node类里next指向下一个节点, value是当前的值,图上面数字是节点中的值,索引的Node是一个指针, 指向原始的节点。 上图的链表数值依次是 2, 5 , 10, 12, 18 , 22, 25, 26。假如在链表中要找是否有12, 需要从单链表头开始遍历,到第4个就找到18。当建立了如上图的2层索引后,首先从第一层索引开始, 2 -> 18 , 18大于12不对,所以第二层索引 2 -> 10 找到10的位置,然后10 ->12 就找到了12。当数据量很大,查找的时间复杂度为O(logn)。图中索引是每隔一个节点建的索引(每隔1个相当于每次减半),你也可以设计每隔3个节点建一个索引。索引层级也要根据数据量增加,单链表也可以改成双链表。

上面分析了跳表搜索的过程,接着聊聊数据插入过程,假如接下来要插入 6、7、 8、 9这几个元素,需要保持跳表节点顺序,可以利用索引找到第二层索引的中2 (第二层索引的10 大于 6, 7, 8 , 9)。插入元素后情况如下图所示:

skip_list

看上图所示,如果需要找9,你会发现查找速度下降,原因是由于插入数据导致原有索引性能退化啦,需要重新生成索引才能保证查找的速度。同样的,删除节点时通过索引快速找到需要删除的节点,删除后也同样需要维持新索引。创建索引会占据一定性能,在插入或者删除数据时,如果没插入或删除一个元素就重新创建索引又有点浪费,所以需要平衡一下,比如记录最底层的索引间的元素个数间隔,超过多少个再重新创建索引。跳表的代码实现自己回去撸吧, 本文先到此为止(哈哈有点复杂,我撸不出来)。

Loading comments box needs to over the wall