概述

二分搜索是一种从排序的项目列表中查找项目的有效算法。它的工作原理是重复将列表中可能包含该项目的部分分成两半，直到将可能的位置缩小到只有一个。

要点

• 二分查找算法的复杂度
  • 时间复杂度- O(logn)
  • 空间复杂度- O(1)

这是搜索算法系列三部分的第二部分。

在上一篇文章《线性搜索》中，我们讨论了为什么搜索在日常生活中如此重要，并讨论了执行搜索的最基本方法；线性搜索。如果您没有机会阅读该文章，我强烈建议您直接跳到该文章并快速阅读。

今天，我们将讨论一种坦率地说是我个人最喜欢的算法的方法；二分查找。

定义

快速回顾一下搜索的定义。

搜索是在数据集中查找某些相关信息的方法。

在讨论线性搜索算法时，我们提到它在大多数情况下效率不是很高，因为它最终会搜索整个数组来查找元素。

由于它不是处理大型数据集最实用的方法，因此我们迫切需要对其进行改进，编程天才们努力寻找一种方法。他们做到了 🙂

在一个非常非常近的星系中，二分搜索诞生了。

二分查找

二分搜索是一种可用于搜索已排序数据集中的元素的算法。所谓排序，是指元素将按照自然递增或递减的顺序排列。

自然顺序是元素的默认顺序。例如，整数的自然递增顺序是1, 2, 3, 4, …，这是它们的值的递增顺序。

A：5 3 12 38 9 45 1 22 3

：1 3 3 5 9 12 22 38 45

在上面的示例中，数组A未排序，因为元素不按值的自然递增或递减顺序排列。而数组B是按自然递增顺序排序的。

简而言之，我们可以说整数数组已排序，如果

arr[i-1] <= arr[i] <= arr[i+1], where 0 < i < size – 1

其中 size 是数组中元素的数量。

类似地，对于字符串，在编程中，自然顺序是字典顺序，或者简单地说，就是如何在英语词典中找到它们。

例如，在英语词典中，“ant”将出现在“art”之前。因此，据说“ant”按词典顺序小于“art”。

假设我们正在尝试在已排序的整数数组中搜索数字K 。为简单起见，我们假设数组按自然递增顺序排序。

假设数组是

1 3 3 5 9 12 22 38 45

我们要寻找的元素K = 12

如果我们应用线性搜索，我们将始终从第一个元素开始，直到找到K或到达数组末尾。

但既然数组在这里排序，我们可以利用它来发挥我们的优势吗？

让我们进行敏锐的观察。

在排序数组中，对于任何索引i，其中0 <= i < size且 size 是数组中元素的数量

如果arr[i] < K

这意味着索引i处的元素小于K。因此，索引i之前的所有元素也将小于K，因为数组已排序。因此，我们可以选择忽略索引i左侧的元素，根本不与K进行比较。

例如，如果i = 2，则 arr[2] = 5。因此，arr[2] < K ，因此我们忽略索引i左侧的元素，即1和3，因为它们也将小于K并且我们永远不会在该侧找到12 。

1 3 3 5 9 12 22 38 45 K = 12

相似地，

如果arr[i] > K

这意味着索引i处的元素大于K。因此，由于数组的排序性质，索引 i之后的所有元素也将大于K对。因此，我们可以选择忽略索引i右侧的元素，根本不将它们与K进行比较。

例如，如果i = 5，则 arr[5] = 12。因此，arr[5] > K ，因此我们忽略索引 i右侧的元素，即22、38和45，因为它们也将大于K并且我们永远不会在该侧找到12 。

1 3 3 5 9 12 22 38 45 K = 11

这意味着如果我们开始搜索任何索引i，并检查该索引处的元素是否小于或大于K ，我们可以选择分别忽略该索引左侧或右侧的特定元素集。

另一方面，

如果arr[i] == K

这意味着索引 i处的元素等于K ，并且我们已经在数组中找到了元素K。因此，我们不需要进一步搜索，我们的工作就完成了。

如果我们选择正确的位置开始搜索，上述观察可以大大减少我们需要搜索的元素数量。

现在出现的问题是选择最佳位置来开始搜索。这就是术语“二进制”的由来。

一元的意思是一。二进制的意思是二。

如果您考虑从数组的中间开始，那么您绝对 100% 正确。

二分查找的工作原理是分而治之。它将数组分为两半，并尝试在其中的一半或另一半中查找元素K ，而不是在两半中查找元素 K。它会继续这样做，直到我们找到该元素或数组耗尽为止。

我们从数组的中间开始搜索，并将数组分成二进制或两个部分。如果中间元素小于K，我们忽略左半部分并对数组的右半部分应用相同的技术，直到找到K或数组无法进一步拆分。

类似地，如果中间元素大于K，我们忽略右半部分并对数组的左半部分应用相同的技术，直到找到K或数组无法进一步拆分。

让我们尝试将这种方法应用于上面的示例。

上面数组的大小为，size = 9

因此，中间元素将位于索引 i = (9 – 1) / 2 = 4

我们将从中间元素开始，索引 i = 4且K = 12

1 3 3 5 9 12 22 38 45 9 < 12，忽略左半部分

，忽略右半部分

，找到K

正如您在上面看到的，我们在第三次比较中发现K = 12 。这比线性搜索方法要好，线性搜索方法需要进行五次比较。

让我们尝试另一个示例，其中 K 可能不存在于列表中，K = 4。

1 3 3 5 9 12 22 38 45 9 > 4，忽略右半部分

，忽略左半部分

，忽略左半部分

，忽略右半部分

没有更多元素可供比较

正如您所看到的，我们找不到K，因为它不存在于数组中。但我们能够确定这只是4 次比较，而线性搜索会比较数组的所有元素。

你：但是拉胡尔，这只是少了5 次比较。所有这些努力只是为了区区 5 次比较：/

Rahul：是的，对于上面的例子，看起来它对于线性搜索来说并不是一个很大的优化。但这是因为数组中的元素数量相当少，准确地说是非常少。当数组包含数百万个元素时，可以看到二分查找的真正威力。

你：具体多少钱？比线性搜索少 10 次比较？😛

拉胡尔：哈哈。好一个。继续阅读以找出答案

算法

下面是二分查找的算法。

1. 初始化n =数组大小，low = 0，high = n-1。我们将使用 low 和 high 来确定我们将在任何给定时间搜索的数组的左端和右端
2. 如果low > high，则意味着我们无法进一步拆分数组，并且无法找到K。我们返回-1表示没有找到元素K
3. else low <= high，这意味着我们将把 low 和 high 之间的数组分成两半，如下所示：
   • 初始化mid = (low + high) / 2，这样我们将数组分成两半，以 arr[mid] 作为中间元素
   • 如果arr[mid] < K，则表示中间元素小于K。因此，mid 左侧的所有元素也将小于K。因此，我们对中右侧重复步骤 2。我们通过设置low = mid+1的值来做到这一点，这意味着我们忽略从 low 到 mid 的所有元素并将数组的左端移动到mid+1
   • 如果arr[mid] > K，则表示中间元素大于K。因此，mid 右侧的所有元素也将大于K。因此，我们对中左侧重复步骤 2。我们通过设置high = mid-1的值来做到这一点，这意味着我们忽略从 mid 到 high 的所有元素并将数组的右端移动到mid-1
   • else arr[mid] == K，这意味着中间元素等于 K 并且我们找到了元素K。因此，我们不需要再寻找了。我们直接从这里返回 mid 表示 mid 是在数组中找到K 的索引

下面是Java 8 中二分查找的实现–

public static void main(String[] args) {
    int[] array = new int[] { 1, 3, 5, 9, 12, 22, 38, 45 };
    int K = 22;
    int res = binarySearch(array, K);

    if (res >= 0) {
        System.out.println(K + " found at index: " + res);
    } else {
        System.out.println(K + " not found");
    }
}

private static int binarySearch(int[] array, int K) {
    int n = array.length;
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        // think: why not use (low + high) / 2 ?
        
        if (array[mid] < K) {
            low = mid + 1;
        } else if (array[mid] > K) {
            high = mid - 1;
        }

        
        else {
            // found K   
            return mid;
        }
    }

    return -1;
}

输出：

22 found at index: 5

时间复杂度

由于我们总是首先从中间元素开始，因此在最好的情况下，数组本身的中间元素可能就是我们要搜索的元素K。

另一方面，如果我们要搜索的元素不存在于数组中，我们将继续将数组分成两半，直到无法再拆分为止，即只剩下一个元素。那么这其中的复杂性是什么呢？

让我们用一个例子来解决这个问题。假设数组的大小为N = 8。

• 第一步，将大小为8的数组从中间分成大小为 4的两部分。

1 2 3 4 | 1 2 3 4 5 6 7 8

• 在第二步中，两个大小为4的数组中的任何一个在中间被分成大小为 2 的两部分。

1 2 | 3 4 或 5 6 | 7 8

• 在第三步中，将四个大小为2的数组中的任何一个在中间分成大小为1的两个部分。

1 | 2 或 3 | 4 或 5 | 6 或 7 | 8

现在，我们只剩下一个无法进一步拆分的元素。

如果您注意到，在每一步中，我们都会丢弃数组的一半，直到找到该元素或没有更多元素可供搜索。

因此我们得出结论，最坏情况的时间复杂度将是我们可以将数组分成两半直到无法进一步拆分的总步骤数。

在上面的例子中，花了3步将数组分成两半，直到只剩下一个元素。

让我们尝试概括这一点。你注意到什么了吗？

取对数（log₂2）两侧，

自从log₂2 = 1

log₂N = 3，将 N 分成两半直到等于 1 的总步数

这与对数的定义完全相同：给出了指数值，我们必须将底数（在我们的例子中为 2）提高到该指数才能产生x（在我们的例子中是数组的大小）。

因此，对于大小为N的数组，需要log₂N步骤将其分成两半，直到只剩下一个元素。

由于上例中数组的长度是 2 的幂，因此log₂N是一个整数。但如果不是2的幂，log₂N将是一个十进制值。因此，我们可以取上限值为log₂N一般来说。

任何数字x的上限值是大于x的最小整数值。例如， 2.5的上限值为3。

通过在这里应用一些基本的高中数学，我们能够得出结论，对于大小为N的数组，二分搜索的最坏情况时间复杂度将为O(ceil(log₂N))。

给你一些观点，如果N = 100000 ，线性搜索最坏情况的复杂度将为O(N) = O。

不太好吧？

另一方面，二分搜索最坏情况的复杂度将是

O(log₂N​) = O(log₂100000) = O(16.6096404744) ~ O(17)

这意味着二分查找只需17 个步骤即可确定数组中是否存在某个元素。它几乎比线性搜索好6000倍。

空间复杂度

正如我们所看到的，我们在二分搜索中没有使用任何大量的额外内存。所以空间复杂度是常数，即O(1)。

PS 用于存储边界、中间索引和其他次要信息的变量是常量，因为它们不依赖于数组的输入大小。

二分查找的应用

如果数组已排序，二分查找显然是赢家。它需要氧（我哦�2氮）O （对数_2​）_在最坏的情况下，线性搜索将在最坏的情况下花费O(N)。

你：但是如果数组没有排序怎么办，Rahul？毕竟我们将无法使用这个很棒的算法。

拉胡尔：是的，你是对的。如果数组没有排序，我们将无法直接使用二分查找。哎呀！我们总是可以对数组进行排序，然后应用二分搜索😀

你：但是排序本身可能需要 O(N*O(log₂N)），然后是一个额外的O(log₂N)用于二分查找。这比线性搜索还要糟糕。

拉胡尔：我很高兴你提到这一点:)

不过你是绝对正确的。如果我们必须对数组进行排序，那么排序和二分查找的总时间复杂度甚至会比线性查找还要多。在这种情况下，线性搜索可能是最好的解决方案。

但是，如果给定一个数组，并且必须对其执行多个（例如 Q 搜索查询）。那么二分查找就是你最好的朋友。

为什么？

因为一旦我们对数组进行了排序，那么我们就可以对排序后的数组一一执行所有查询。因为，每个二分搜索查询只需要O（log₂N​）最坏情况下，对于 Q 个查询，需要 * O(Qlog₂N）**。

因此，如果我们使用良好的排序算法，例如归并排序或堆排序，其保证的时间复杂度为* O(Nlog₂N）**，总时间复杂度为

二分查找= O(Nlog₂ + Qlog₂N) = O((N+Q) *log₂N)**

如果我们假设查询的数量等于数组中元素的数量，那么上面的等式就变成了

二分查找= O(N * log₂N）

另一方面，如果我们使用线性搜索，那么在最坏的情况下每个查询将花费 O(N)，并且 Q 个查询的总时间复杂度将是

线性搜索= O(N * N) = O(）

正如我们所看到的，如果数组未排序并且查询数量巨大（这是现实生活中更可能发生的情况），二分搜索的性能比线性搜索要好得多。

结论

今天我们学习了一个绝对传奇的算法。除了搜索之外，二分搜索还有很多应用。