目录

数据结构和算法 | 二分查找大家都会,那么二分查找的变体呢?【6】

1. 前言

大家好,我是多选参数的程序锅,一个正在”捣鼓“操作系统、学数据结构和算法以及 Java 的硬核菜鸡。

二分查找大家估计都会,但是二分查找的变体大家会吗?我相信你是会的,我这个菜鸡就是不会了,所以在学习二分查找变体的时候,我感觉发现了新大陆。

为了整个知识的相对完整,下面还是从最基本的二分查找开始讲解,之后讲解二分查找的变体,这个变体在刷 Leetcode 的有些题目的时候也会用到。最后对二分查找这种算法进行总结。

本篇相关的代码都可以从 https://github.com/DawnGuoDev/algorithm 获取,另外,该仓库除了包含了基础的数据结构和算法实现之外,还会有数据结构和算法的笔记、LeetCode 刷题记录(多种解法、Java 实现) 、一些优质书籍整理。

https://img.dawnguo.cn/Algorithm/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.png

2. 二分查找及其变体

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

由于经过一次查找,会剔除一半数据而剩下另一半数据,因此经过 k 次查找之后,剩下的数据个数为 $n*\frac{1}{2^k}$,整个二分查找当剩下一个元素的时候停止,**因此需要经过 $log_2^n$ 次查找,时间复杂度也就是 $O(logn)$。**

2.1. 最基础的实现

这边先讲解不存在重复元素的有序数组中,查找值等于给定值的元素的情况(PS:全文的讲解都以数据是从小到大排列为前提)。

2.1.1. 非递归的方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public int bsearch(int[] array, int len, int value) {
    int low = 0;
    int high = len - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (array[mid] == value) {
            return mid;
        } else if (array[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

在实现非递归算法时,需要注意以下几个关键点:

  • 循环的条件是 low <= high,而不是 low < high。因为可能 low 和 high 重合的时候正是需要查询的值,比如 1,2,3 那么假如我要查询 3 这个值的位置时,是在 low 等于 high 的时候才查询到的。
  • mid = (low+high)/2 这种写法不太严谨,因为 low 和 high 比较大的时候,可能就会溢出。所以,改进的方法是 mid = low +(high-low)/2。当然为了追求性能的极致,那么可以将这里的除以 2 改为移位操作。因为移位操作比除法运算来说,计算机处理前者会更快。最终为 mid = low + ((high-low)>>1)。需要注意的是,考虑到移位操作和加法的优先级,这边的括号必须要这样。
  • low 和 high 值的更新,这边一定要记得 +1 和 -1,否则的话可能会进入死循环。假如没有+1 或者 -1 的操作,那么 1,2,3 我要查询的是 3 这个值,第一步 low=0, high=2;第二步 low=1,high=2;第三步还是 low=1,high=2。

2.1.2. 递归的方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public int bsearchInternally(int[] array, int low, int high, int value) {
    if (low > high) {
        return -1;
    }

    int mid = low + ((high -  low) >> 1);
    if (array[mid] == value) {
        return mid;
    } else if (array[mid] < value) {
        return bsearchInternally(array, mid + 1, high, value);
    } else {
        return bsearchInternally(array, low, mid - 1, value);
    }
}

这边的注意点与非递归的注意点是一一对应的,递归方式注意的是循环的条件,非递归方式注意的则是递归终止的条件,这边需要 low>high 而不是 low >= high,理由是一样的,自己举例看一下。其他两个注意事项是一样的。

回忆一下递归方式编写代码的技巧:1.是先写出递归式;2.确定终止条件;3.翻译成代码。

2.2. 查找第一个等于给定值的元素所在的 index

接下去讲解二分查找的变体,主要考虑几种典型的情况。首先,将不存在重复元素的有序数组进行一般化,即有序数组集合中存在重复的数据。那么我们该如何找到第一个等于给定值的数据的 index 呢?

假如按照最简单的方式来实现查找的话(即上述的实现),那么得到的结果将不一定正确。比如下面这个存在重复数据的有序数组集合。假设要查找的数据是 8 ,那么先拿 8 和第 4 个数据 6 进行比较,发现 8 比 6 大,于是在下标 5-9 之间寻找。结果发现第 7 个数据 8 正好是要查找的数据,然后将 index 7 返回,但是实际上第一个 8 的 index 应该是 5。

1
1  3  4  5  6  8  8  8  11  18

因此,对于这个变形问题,我们需要改造一下之前的代码。改造之后的代码如下所示:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public int bsearchFirstEqual(int[] array, int len, int value) {
    int low = 0;
    int high = len - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (array[mid] < value) {
            low = mid + 1;
        } else if (array[mid] > value) {
            high = mid - 1;
        } else {
            if (mid == 0 || array[mid - 1] != value) {
                return mid;
            }
            high = mid - 1;
        }
    }
    return -1;
}

这边稍微解析一下代码。a[mid]跟要查找的 value 的大小关系有三种情况:大于、小于、等于。对于 a[mid] >value的情况,说明等于情况位于 low-mid 之间,所以 high = mid-1。对于 a[mid]<value 的情况,说明等于情况位于 mid-high 之间,所以 low = mid+1。对于 a[mid]=value的情况,我们需要确保 mid 这个 index 是不是第一个等于 value 的 index。因此,先判断 mid 等不等于 0,假如等于的话,那么肯定是第一个了;之后判断 mid-1 位置的元素等不等于 value,如果不等于 value,那么说明 mid 是第一个等于 value 的 index。假如 mid-1 位置的元素等于 value,那么说明第一个等于 value 在 mid 之前,所以 high=mid-1

2.3. 查找最后一个等于给定值的元素所在的 index

前面是查找第一个值等于给定值的元素,现在将问题稍微改一下,查找最后一个值等于定值的元素的 index。相应的实现代码其实和前面的类似。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public int bsearchLastEqual(int[] array, int len, int value) {
    int low = 0;
    int high = len - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);

        if (array[mid] < value) {
            low = mid + 1;
        } else if (array[mid] > value) {
            high = mid - 1;
        } else {
            if (mid == len -1 || array[mid + 1] != value) {
                return mid;
            }
            low = mid + 1;
        }
    }

    return -1;
}

这里我们就不分析了,分析思路跟上面的那种情况类似。

2.4. 查找第一个大于等于给定值的元素所在的 index

看完查找值相等的情况之后,接下去我们查找值不相等的情况。在有序数组中(可含重复元素),查找第一个大于等于给定值的元素的 index。比如针对序列:3、4、6、7、10,查找第一个大于等于 5 的元素,那就是 6 ,index 是 2。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public int bsearchFirstMore(int[] array, int len, int value) {
    int low = 0; 
    int high = len - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);

        if (array[mid] < value) {
            low = mid + 1;
        } else {
            if (mid == 0 || array[mid - 1] < value) {
                return mid;
            }
            high = mid - 1;                
        }
    }

    return -1;
}

如果 mid 位置所在的元素小于 value,那么第一个大于等于 value 的值的 index 是在 [mid+1, high] 之间,所以 low=mid+1。如果 mid 位置所在的元素已经大于 value,那么需要判断 mid 是不是第一个大于等于 value 的 index。假如 mid == 0 ,那么肯定是第一个了;或者 mid 前面的那个元素小于 value,那么 mid 也是第一个大于等于 value 的 index。如果两个条件都不满足,那么第一个大于等于 value 的 index,是在 [low, mid-1] 之间,因此将 high 进行更新。

2.5. 查找最后一个小于等于给定值的元素所在的 index

现在将问题变成查找最后一个小于等于给定值的元素的 index。比如针对序列:3、5、6、8、9、10,最后一个小于等于给定值 7 的元素是 6, index 是 2 。代码的实现思路与上述情况相似。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public int bsearchLastLess(int[] array, int len, int value) {
    int low = 0;
    int high = len - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);

        if (array[mid] > value) {
            high = mid - 1;
        } else {
            if (mid == len - 1 || array[mid + 1] > value) {
                return mid;
            }
            low = mid + 1;
        }
    }

    return -1;
}

这里我们就不分析了,分析思路跟上面的那种情况类似。

3. 总结

3.1. 二分查找的局限性

虽然二分查找的时间复杂度是 O(logn),查找效率极高,但是二分查找却不是完美的,这种查找方法存在一些局限性。

  • 二分查找依赖的是顺序表结构,简单点说就是数组。

    二分查找能否依赖其他数据结构呢?比如链表。答案是不可以的,主要原因是二分查找算法是按照下标随机访问元素的,比如我们访问 mid 这个位置的数据就是通过下标随机访问的,这个时间复杂度是 O(1)。假如使用链表方式的话,需要遍历到 mid 这个位置,那么时间复杂度为 O(n)。所以,如果数据使用链表存储,二分查找的时间复杂度会变得高。

  • 二分查找针对的是有序数据,在动态变化的数据集合中不适用

    二分查找的时候要求查找的数据序列必须是有序的。如果数据不是有序的,那么需要先排序才能查找。在使用时间复杂度为 O(nlogn)的排序算法的情况下。如果一组静态的数据,没有频繁地插入、删除等操作,二分查找还是可以接受的。因为我们可以进行一次排序,多次二分查找。这样排序的成本就会被均摊。但是,如果我们的数据集合有频繁的插入和删除操作的话,要想二分查找。那么每次插入、删除之后都需要进行排序,从而反正数据序列的有序。这种情况下,维护有序的时间成本时很高的。

    综上,二分查找只能用于插入、删除操作不频繁,一次排序多次查找的情况。针对动态变化的数据集合,二分查找将不再适合。

  • 数据量太小不适合二分查找

    要处理的数据量很小的话,完全没有必要用二分查找,顺序遍历就可以了。比如要在 10 个有序的数组中查找一个元素,不管使用顺序遍历还是二分查找,查找速度都查不多。但是这种情况下有个例外,就是如果比较操作非常耗时的话,那么也请用二分查找,因为虽然两者次数差不多,但是这种情况下我们是需要尽可能减少比较的次数。显然,二分查找的次数还会更少一点。

  • 数据量太大也不适合二分查找

    二分查找的底层需要依赖数组这种数据结构,而数组这种数据结构要求内存空间的连续。假如数据量太大,比如有 1GB 大小的数据,如果使用数组来存储,那么就需要 1GB 的连续内存空间。所以当要查找的数据集合特别大的时候二分查找也会不太适合。

3.2. 二分查找的优势

  • 二分查找在内存使用上更节省

    虽然大部分情况下,用二分查找的方式可以解决的问题,散列表、二叉树都可以解决。但是,不管是散列表还是二叉树都需要额外的内存空间。而二分查找依赖的是数组,除了数据本身之外,不需要存储额外的其他信息。所以当二分查找需要 100MB 内存的情况下,散列表或二叉树需要的内存空间会更大(不止 100MB)。显然,在这三种方式中二分查找是最省内存空间的。

  • 二分查找更适合用在“近似”查找问题。

    在这类问题上,二分查找的优势更加明显,就比如这几种变体。而查找“等于给定值”的问题,更适合散列表或二叉树。这种变体的二分查找算法比较难写,尤其是细节上如果处理不好容易产生BUG,这些出错的细节有:终止条件、区间上下界更新方法、返回值选择。

巨人的肩膀

  1. 极客时间专栏,王争老师的《数据结构与算法之美》

附 Github

整个系列的代码可查看 github 仓库 https://github.com/DawnGuoDev/algos ,这个仓库将主要包含常用数据结构及其基本操作的手写实现(Java),也会包含常用算法思想经典例题的实现(Java)。在接下来一年内,这个仓库将会保持更新状态,在此之间学到的关于数据结构和算法的知识或者实现也都会往里面 commit,所以赶紧来 star 哦。