二分查找与Redis跳表

二分查找

时间复杂度O(logn)

这是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效

比如2的32次方，找一个数，最多比较32次，而常数级可以是O(1000)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}
/var/www/html/veleap/controllers/web/MatchController.php

优化mid 的计算方式：

low+(high-low)/2防止(low+high)溢出

更进一步优化：

除以 2 操作转化成位运算，

low+((high-low)>>1)，因为相比除法运算来说，计算机处理位运算要快得多

二分查找局限性：

1
2
3
4
5
6
7
1二分查找依赖的是顺序表结构,即数组。主要原因是二分查找算法需要按照下标随机访问元素，而链表随机访问的时间复杂度是 O(n)

2二分查找针对的是有序数据，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用

3数据量太小不适合二分查找，比如10个数据，顺序遍历就足够了，只有数据量比较大的时候，二分查找的优势才会比较明显。例外的是，如果数据之间的比较操作非常耗时，不管数据量大小，都推荐使用二分查找

4数据量太大也不适合二分查找，比如1GB数据量，数组为了支持随机访问的特性，要求内存空间连续，而不是零散的

那么，如何在 1000 万个整数中快速查找某个整数？

1
2
内存限制是 100MB,每个数据大小是 8 字节,存储为数据后，内存占用80MB,先排序，再二分查找
另外，散列表和二叉树不可用，因为它们都会需要比较多的额外的内存空间，100MB是不够的

二分查找的变形问题：

1
2
3
4
5
6
7
1查找第一个值等于给定值的元素（存在重复数据）

2查找最后一个值等于给定值的元素

3查找第一个大于等于给定值的元素

4查找最后一个小于等于给定值的元素

可参考leetcode34题

1查找第一个值等于给定值的元素（存在重复数据）

2查找最后一个值等于给定值的元素,类似第一个问题

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;
}

3查找第一个大于等于给定值的元素

4查找最后一个小于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

那么，如何快速定位出一个 IP 地址的归属地？

可以将ip转为32位整型，再排序

1
ip地址本身就是32位标识，只需要将按点拆成数组。将数组元素转换成int值，只有移动对应的位数即可：arr[0]左移24位，arr[1]左移16位，arr[2]左移8位，arr[3]左移0位

用数组，直接下标找归属地，为啥还用二分查找，绕道？

总结：

凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省，但是毕竟内存如此紧缺的情况并不多，二分查找的场景中，“值等于给定值”不多，更多的是在大于小于等“近似值”问题，优势更明显

Redis跳表

这种链表加多级索引的结构，就是跳表（空间换时间），Redis 中的有序集合（Sorted Set）就是用跳表来实现的

跳表的查询的时间复杂度是O(logn)，插入、删除操作的时间复杂度也是 O(logn)

两节点一个索引算,索引的结点总和是 n/2+n/4+n/8…+8+4+2=n-2，即n个节点的链表，需要建立近n个索引，空间复杂度为O(n)。若是三节点一个索引，则索引总数是n/2,节省了一半的空间。

1
等比数列求和 n/2, n/4, ... , 2 这个数列中一共有 log(n/2) 项 等比数列求和公式 S = a0(1-q^n)/(1-q), 其中 a0 表示首项，n 表示项数 这里的 a0=n/2, 项数=log(n/2), q=1/2 S = (n/2)*(1-2/n)/(1-1/2) = n-2

实际开发中，不必太在意索引占用的额外空间，因为原始链表中存储的可能是很大的对象，而索引存储的是关键值和指针，几乎可以忽略不计。

问题：

为什么 Redis 要用跳表来实现有序集合，而不是红黑树？

1
2
3
4
5
6
7
严格讲，Redis 中的有序集合除了跳表 还使用了散列表

1有序集合支持的核心功能有插入、删除、查找、按区间查找（比如查找值在[100, 356]之间的数据）、迭代输出有序序列。其中区间查找，红黑数的效率没有跳表高

2跳表的实现不简单，但比红黑树容易，更好懂好写，简单意味着可读性好，不容易出错

3跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

当然，跳表不能完全取代红黑树，因为红黑树出现的早，已有很多编程语言中都有封装，例如Map类型，而跳表没有现成的实现，需要自己写

redis中删除了索引上的数据，是否需要重新建立索引？

1
答：而跳表是通过随机函数来维护索引的“平衡性”，比如，插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。红黑树、AVL树通过左右旋的方式保持左右子树的大小平衡

以上学于极客时间，做的笔记