简述
二分查找(Binary Search)是一种针对有序数据集合的查找算法。
跳表(Skip List)是一种优秀的动态数据结构,支持快速的插入、删除、查找操作。
二分查找(Binary Search)
原理:通过每次跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到待查找元素,或者区间被缩小为0。
时间复杂度:O(logn)。
最简单的二分:
1 | //二分查找的普通实现(简单版) |
要点:
- 循环退出条件,是low <= high,而不是low < high;
- mid的取值通常为(low+high)/2,但是可以写为low+(high-low)/2,为了提高效率,除以2可以写为右移一位,即low+((high-low)>>1);
- low和high的下标要常更新。
局限性:依赖顺序表结构;数据必须是有序的;数据量很小时时间和顺序遍历差别不大;数据量太大时数组连续内存可能不够。
变种1:查找第一个值等于给定值的元素(提示:判断下标是否等于0,或者某下标的前一节点是否等于给定值)。
参考代码:
1 | public int bsearch(int[] a, int n, int value) { |
变种2:查找最后一个值等于给定值的元素(提示:判断下标是否等于0,或者某下标的后一节点是否等于给定值)。
变种3:查找第一个子节点大于等于给定值的元素(提示某下标的前一节点是否小于给定值)。
变种4:查找最后一个小于等于给定值得元素(提示:某下标的后一节点是否大于给定值)。
二分查找总结
一般情况下,凡是可以用二分查找解决的,绝大部分都倾向于使用散列表或者二叉查找树,即使二分查找在内存使用上更节省。但是一般对于近似查找,二分查找的优势比较明显。
跳表(Skip list)
原理:对要查找的数据进行索引操作,一般情况下,两个节点中间都会有一个索引节点;
时间复杂度:O(logn)
空间复杂度:O(n)
两个节点中间都有一个节点则第一层索引有n/2个节点;第二层有n/4个节点,k级有n/(2^k)……假设索引有h级,最高级有2个节点,则n/2^h=2,从而求得h=log2n - 1,如果包含原始链表,则h = log2n,如果每一层都要遍历m个节点,则跳表中查询一个数据的时间复杂度是(m logn),再加上每一层需要遍历的节点不超过3个节点,所以算出时间复杂度是O(logn)。
动态插入和删除:
主要时间耗费在插入位置的查找上,所以是O(logn)。
跳表索引动态更新:
插入数据时,根据随机函数,来决定将这个节点插入到哪几级索引中,以此来维护索引平衡性,不至于使得两个索引节点之间包含大量节点。
参考
本节相关的学习代码参考github: