查找-二分查找

acc8226

发布于 2022-05-17 15:47:02

9300

发布于 2022-05-17 15:47:02

文章被收录于专栏：叽叽西

今天我们讲一种针对有序数据集合的查找算法：二分查找（Binary Search）算法，也叫折半查找算法。

老规矩，我们还是来看一道思考题。假设我们有 1000 万个整数数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这 1000 万数据中？我们希望这个功能不要占用太多的内存空间，最多不要超过 100MB，你会怎么做呢？带着这个问题，让我们进入今天的内容吧！带着这个问题，让我们进入今天的内容吧！

无处不在的二分思想

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

O(logn) 惊人的查找速度

二分查找是一种非常高效的查找算法，高效到什么程度呢？我们来分析一下它的时间复杂度。我们假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。

可以看出来，这是一个等比数列。其中 n/2k=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。

二分查找是我们目前为止遇到的第一个时间复杂度为 O(logn) 的算法。后面章节我们还会讲堆、二叉树的操作等等，它们的时间复杂度也是 O(logn)。我这里就再深入地讲讲 O(logn) 这种对数时间复杂度。这是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效。为什么这么说呢？因为 logn 是一个非常“恐怖”的数量级，即便 n 非常非常大，对应的 logn 也很小。

二分查找的递归与非递归实现

实际上，简单的二分查找并不难写，注意我这里的“简单”二字。下一节，我们会讲到二分查找的变体问题，那才是真正烧脑的。今天，我们来看如何来写最简单的二分查找。

最简单的情况就是有序数组中不存在重复元素，我们在其中用二分查找值等于给定值的数据。我用 Java 代码实现了一个最简单的二分查找算法。

public static int bsearch(int[] array, int value) {
    int start = 0;
    int end = array.length - 1;
    int mid;
    int find = -1;
    while (start <= end) {
        mid = start + ((end - start) >>> 1);
        if (array[mid] == value) {
            find = mid;
            break;
        } else if (array[mid] < value) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return find;
}

这个代码我稍微解释一下，low、high、mid 都是指数组下标，其中 low 和 high 表示当前查找的区间范围，初始 low=0， high=n-1。mid 表示[low, high]的中间位置。我们通过对比 a[mid]与 value 的大小，来更新接下来要查找的区间范围，直到找到或者区间缩小为 0，就退出。如果你有一些编程基础，看懂这些应该不成问题。现在，我就着重强调一下容易出错的 3 个地方。

1. 循环退出条件 注意是 low<=high，而不是 low<high。

2.mid 的取值 实际上，mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是将 mid 的计算方式写成 low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。

3.low 和 high 的更新 low=mid+1，high=mid-1。注意这里的 +1 和 -1

实际上，二分查找除了用循环来实现，还可以用递归来实现，过程也非常简单。我用 Java 语言实现了一下这个过程，正好你可以借此机会回顾一下写递归代码的技巧。

// 二分查找的递归实现
private static int bsearchInternally(int[] a, int low, int high, int value) {
    int find = -1;
    if (low <= high) {
        int mid = low + ((high - low) >>> 1);
        if (a[mid] == value) {
            find = mid;
        } else if (a[mid] < value) {
            find = bsearchInternally(a, mid + 1, high, value);
        } else {
            find = bsearchInternally(a, low, mid - 1, value);
        }
    }
    return find;
}

二分查找应用场景的局限性

前面我们分析过，二分查找的时间复杂度是 O(logn)，查找数据的效率非常高。不过，并不是什么情况下都可以用二分查找，它的应用场景是有很大局限性的。那什么情况下适合用二分查找，什么情况下不适合呢？

首先，二分查找依赖的是顺序表结构，简单点说就是数组。其次，二分查找针对的是有序数据。再次，数据量太小不适合二分查找。最后，数据量太大也不适合二分查找。

解答开篇

二分查找的理论知识你应该已经掌握了。我们来看下开篇的思考题：如何在 1000 万个整数中快速查找某个整数？

这个问题并不难。我们的内存限制是 100MB，每个数据大小是 8 字节，最简单的办法就是将数据存储在数组中，内存占用差不多是 80MB，符合内存的限制。借助今天讲的内容，我们可以先对这 1000 万数据从小到大排序，然后再利用二分查找算法，就可以快速地查找想要的数据了。

四种常见的二分查找变形问题

上面介绍的二分查找是最简单的一种，即有序数据集合中不存在重复的数据，我们在其中查找值等于某个给定值的数据。如果我们将这个问题稍微修改下，有序数据集合中存在重复的数据，我们希望找到第一个值等于给定值的数据，这样之前的二分查找代码还能继续工作吗？

变体一：查找第一个值等于给定值的元素

public static int searchFirstEquals(int[] a, int value) {
    int low = 0;
    int high = a.length - 1;
    int mid;
    int find = -1;
    while (low <= high) {
        mid = low + ((high - low) >>> 1);
        if (a[mid] == value) {
            if (mid == 0 || a[mid - 1] != value) {
                find = mid;
                break;
            } else {
                high = mid - 1;
            }
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return find;
}

我来稍微解释一下这段代码。a[mid]跟要查找的 value 的大小关系有三种情况：大于、小于、等于。对于 a[mid]>value 的情况，我们需要更新 high= mid-1；对于 a[mid]<value 的情况，我们需要更新 low=mid+1。这两点都很好理解。那当 a[mid]=value 的时候应该如何处理呢？

如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；如果 mid 不等于 0，但 a[mid]的前一个元素 a[mid-1]不等于 value，那也说明 a[mid]就是我们要找的第一个值等于给定值的元素。

如果经过检查之后发现 a[mid]前面的一个元素 a[mid-1]也等于 value，那说明此时的 a[mid]肯定不是我们要查找的第一个值等于给定值的元素。那我们就更新 high=mid-1，因为要找的元素肯定出现在[low, mid-1]之间。

变体二：查找最后一个值等于给定值的元素

public static int searchLastEquals(int[] a, int value) {
    int low = 0;
    int high = a.length - 1;
    int mid;
    int find = -1;
    while (low <= high) {
        mid = low + ((high - low) >>> 1);
        if (a[mid] == value) {
            if (mid == high || a[mid + 1] != value) {
                find = mid;
                break;
            } else {
                low = mid + 1;
            }
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return find;
}

变体三：查找第一个大于等于给定值的元素

现在我们再来看另外一类变形问题。在有序数组中，查找第一个大于等于给定值的元素。实际上，实现的思路跟前面的那两种变形问题的实现思路类似，代码写起来甚至更简洁。

public static int searchFirstGreateThanEquals(int[] a, int value) {
    int low = 0;
    int high = a.length - 1;
    int mid;
    int find = -1;
    while (low <= high) {
        mid = low + ((high - low) >>> 1);
        if (a[mid] >= value) {
            if (mid == 0 || !(a[mid - 1] >= value)) {
                find = mid;
                break;
            } else {
                high = mid - 1;
            }
        } else {
            low = mid + 1;
        }
    }
    return find;
}

变体四：查找最后一个小于等于给定值的元素

public static int searchLastLessThanEquals(int[] a, int value) {
    int low = 0;
    int high = a.length - 1;
    int mid;
    int find = -1;
    while (low <= high) {
        mid = low + ((high - low) >>> 1);
        if (a[mid] <= value) {
            if (mid == high || !(a[mid + 1] <= value)) {
                find = mid;
                break;
            } else {
                low = mid + 1;
            }
        } else {
            high = mid - 1;
        }
    }
    return find;
}

内容小结

我的代码 https://gitee.com/kaiLee/struct/tree/master/src/main/java/com/s7/search

今天我们学习了一种针对有序数据的高效查找算法，二分查找，它的时间复杂度是 O(logn)。

二分查找的核心思想理解起来非常简单，有点类似分治思想。即每次都通过跟区间中的中间元素对比，将待查找的区间缩小为一半，直到找到要查找的元素，或者区间被缩小为 0。但是二分查找的代码实现比较容易写错。你需要着重掌握它的三个容易出错的地方：循环退出条件、mid 的取值，low 和 high 的更新。

二分查找虽然性能比较优秀，但应用场景也比较有限。底层必须依赖数组，并且还要求数据是有序的。对于较小规模的数据查找，我们直接使用顺序遍历就可以了，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

大部分情况下，用二分查找可以解决的问题，用散列表、二叉树都可以解决。但是，我们后面会讲，不管是散列表还是二叉树，都会需要比较多的额外的内存空间。而二分查找底层依赖的是数组，除了数据本身之外，不需要额外存储其他信息，是最省内存空间的存储方式。

上面我说过，凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省，但是毕竟内存如此紧缺的情况并不多。那二分查找真的没什么用处了吗？

实际上，求“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如今天讲的这几种变体问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。

变体的二分查找算法写起来非常烧脑，很容易因为细节处理不好而产生 Bug，这些容易出错的细节有：终止条件、区间上下界更新方法、返回值选择。所以今天的内容你最好能用自己实现一遍，对锻炼编码能力、逻辑思维、写出 Bug free 代码，会很有帮助。

课后思考

我们今天讲的都是非常规的二分查找问题，今天的思考题也是一个非常规的二分查找问题。如果有序数组是一个循环有序数组，比如 4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法呢？

解答：我们发现循环数组存在一个性质：以数组中间点为分区，会将数组分成一个有序数组和一个循环有序数组。如果首元素小于 mid，说明前半部分是有序的，后半部分是循环有序数组；如果首元素大于 mid，说明后半部分是有序的，前半部分是循环有序的数组；如果目标元素在有序数组范围中，使用二分查找；如果目标元素在循环有序数组中，设定数组边界后，使用以上方法继续查找。

 时间复杂度为 O(logN)。

private static int search(int[] array, int low, int high, int value) {
    int find = -1;
    if (low <= high) {
        int mid = low + ((high - low) >>> 1);
        if (array[mid] == value) {
            find = mid;
        } else {
            // 左边有序，右边依旧循环
            if (array[low] < array[mid]) {
                if (array[low] <= value && value <= array[mid]) {
                    // 此处建议采用二分查找，当然也可以继续递归使用 search 方法
                    find = search(array, low, mid - 1, value);
                } else {
                    find = search(array, mid + 1, high, value);
                }
            } 
            // 右边边有序，左边依旧循环
            else {
                // 此处建议采用二分查找，当然也可以继续递归使用 search 方法
                if (array[mid] <= value && value <= array[high]) {
                    find = search(array, mid + 1, high, value);
                } else {
                    find = search(array, low, mid - 1, value);
                }
            }
        }
    }
    return find;
}