数据结构和算法-二分查找和跳表

简述

二分查找(Binary Search)是一种针对有序数据集合的查找算法。

跳表(Skip List)是一种优秀的动态数据结构,支持快速的插入、删除、查找操作。

二分查找(Binary Search)

原理:通过每次跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到待查找元素,或者区间被缩小为0。

时间复杂度:O(logn)。

最简单的二分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//二分查找的普通实现(简单版)
public int bsearch(int[] a, int n, int value){
int low = 0;
int high = n - 1;
while(low <= high){
int mid = (low + high) /2;
if(a[mid] == value){
return mid;
} else if(a[mid] < value){
low = mid + 1;
} else {
high = mid -1;
}
}
return -1;
}
//二分查找的递归实现
public int bsearch(int[] a, int high,int low, int value){
if(low > high) return -1;
int mid = low + ((high - low) >> 1);
if(a[mid] == value)
return mid;
else if(a[mid] < value)
bsearch(a,high,mid + 1,value);
else
bsearch(a,high - 1,mid,value);
}

要点:

  1. 循环退出条件,是low <= high,而不是low < high;
  2. mid的取值通常为(low+high)/2,但是可以写为low+(high-low)/2,为了提高效率,除以2可以写为右移一位,即low+((high-low)>>1);
  3. low和high的下标要常更新。

局限性:依赖顺序表结构;数据必须是有序的;数据量很小时时间和顺序遍历差别不大;数据量太大时数组连续内存可能不够。

变种1:查找第一个值等于给定值的元素(提示:判断下标是否等于0,或者某下标的前一节点是否等于给定值)。
参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}

变种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:

https://github.com/liuhuijun11832/algorithm

坚持原创、技术分享。请作者喝杯茶吧!