二分查找

发表于 | 分类于 | 阅读数

简单记录下二分查找和跳表的知识

二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。 每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。

时间复杂度

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

因为logn是一个非常“恐怖”的数量级，即便n非常非常大，对应的logn也很小。比如n等于2的32次方，大约是42亿。也就是说，如果我们在42亿个数据中用二分查找一个数据，最多需要比较32次。

用大O标记法表示时间复杂度的时候，会省略掉常数、系数和低阶。对于常量级时间复杂度的算法来说，O(1)有可能表示的是一个非常大的常量值，比如O(1000)、O(10000)。所以，常量级时间复杂度的算法有时候可能还没有O(logn)的算法执行效率高。

局限性

依赖数组

二分查找依赖的是顺序表结构，简单点说就是数组。主要原因是二分查找算法需要按照下标随机访问元素。数组按照下标随机访问数据的时间复杂度是O(1)，而链表随机访问的时间复杂度是O(n)。所以，如果数据使用链表存储，二分查找的时间复杂就会变得很高。

由此可能会引发第二个问题，数据量过大也不适合二分查找。数组需要内存空间的连续，对内存的要求比较苛刻。

有序数据

数据必须是有序的。如果数据没有序，我们需要先排序。

递归实现示例

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int bSearchInternally(int[] nums, int left, int right, int value) {
    if (left > right) {
        return -1;
    }
    int mid = left + ((right - left) >> 1);
    if (nums[mid] == value) {
        return mid;
    } else if (nums[mid] < value) {
        return bSearchInternally(nums, mid + 1, right, value);
    } else {
        return bSearchInternally(nums, left, mid - 1, value);
    }
}

循环实现示例

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public static int bSearch(int[] nums, int value) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == value) {
            return mid;
        } else if (nums[mid] < value) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

public static int bSearch2(int[] nums, int value) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= value) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (left < nums.length && nums[left] == value) {
        return left;
    } else {
        return -1;
    }
}

public static int bSearch3(int[] nums, int value) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] > value) {
            right = mid - 1;
        } else if (nums[mid] < value) {
            left = mid + 1;
        } else if (mid == 0 || nums[mid - 1] != value) {
            return mid;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

跳表

跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是O(logn)。

跳表的空间复杂度是O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，实现要简单多了。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向用跳表。

为什么Redis会使用跳表实现有序集合而不是红黑树

Redis中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。我们现在暂且忽略这部分。Redis的开发手册中的有序集合支持的核心操作主要有下面这几个:

  • 插入一个数据;
  • 删除一个数据;
  • 查找一个数据;
  • 按照区间查找数据(比如查找值在[100, 356]之间的数据);
  • 迭代输出有序序列。

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。

  • 按照区间来查找数据这个操作，红黑树的效率没有跳表高。对于按照区间查找数据这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。
  • 跳表更容易代码实现。虽然跳表的实现也不简单，但比起红黑树来说还是好懂、好写多了，而简单就意味着可读性好，不容易出错。
  • 跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
投食入口