二分查找

目标：快速找到数组中的元素。

假设您有一个数字数组，并且您想要确定该数组中是否存在特定数字，如果是，则位于哪个索引处。

在大多数情况下，Swift 的Collection.index(of:)功能足以满足：

let numbers \= \[11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 41, 23\]

numbers.index(of: 43)  // returns 15

内置Collection.index(of:)函数执行线性搜索。在看起来像这样的代码中：

func linearSearch<T: Equatable\>(\_ a: \[T\], \_ key: T) \-> Int? {
    for i in 0 ..< a.count {
        if a\[i\] \== key {
            return i
        }
    }
    return nil
}

你会这样使用它：

linearSearch(numbers, 43)  // returns 15

所以有什么问题？linearSearch()从头开始循环遍历整个数组，直到找到您要查找的元素。在最坏的情况下，该值甚至不在数组中，并且所有工作都白费了。

平均而言，线性搜索算法需要查看数组中一半的值。如果你的数组足够大，这就会开始变得非常慢！

分而治之

加快速度的经典方法是使用二分搜索。诀窍是不断将数组分成两半，直到找到该值。

对于大小为 的数组n，性能不像线性搜索那样为O(n) ，而仅为O(log n)。从长远来看，对具有 1,000,000 个元素的数组进行二分搜索只需大约 20 个步骤即可找到您要查找的内容，因为log_2(1,000,000) = 19.9. 对于具有 10 亿个元素的数组，只需 30 步。（话又说回来，您最后一次使用包含 10 亿个项目的数组是什么时候？）

听起来不错，但使用二分搜索有一个缺点：数组必须排序。实际上，这通常不是问题。

二分查找的工作原理如下：

• 将数组分成两半，并确定您要查找的内容（称为搜索键）是在左半部分还是在右半部分。
• 如何确定搜索键位于哪一半？这就是为什么你首先对数组进行排序，这样你就可以进行简单的<或>比较。
• 如果搜索关键字位于左半部分，则在那里重复该过程：将左半部分分成两个更小的部分，然后查找搜索关键字必须位于哪一部分。（当它是右半部分时也是如此。）
• 重复此过程直到找到搜索关键字。如果数组无法进一步拆分，您必须遗憾地得出结论：搜索键不存在于数组中。

现在您知道为什么它被称为“二元”搜索：在每一步中，它都会将数组分成两半。这种分而治之的过程使其能够快速缩小搜索关键字的范围。

代码

下面是 Swift 中二分查找的递归实现：

func binarySearch<T: Comparable\>(\_ a: \[T\], key: T, range: Range<Int\>) \-> Int? {
    if range.lowerBound \>= range.upperBound {
        // If we get here, then the search key is not present in the array.
        return nil

    } else {
        // Calculate where to split the array.
        let midIndex \= range.lowerBound + (range.upperBound \- range.lowerBound) / 2

        // Is the search key in the left half?
        if a\[midIndex\] \> key {
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)

        // Is the search key in the right half?
        } else if a\[midIndex\] < key {
            return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)

        // If we get here, then we've found the search key!
        } else {
            return midIndex
        }
    }
}

要尝试此操作，请将代码复制到游乐场并执行以下操作：

let numbers \= \[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67\]

binarySearch(numbers, key: 43, range: 0 ..< numbers.count)  // gives 13

请注意，该numbers数组已排序。否则二分查找算法就无法工作！

我说过二分查找的工作原理是将数组分成两半，但我们实际上并没有创建两个新数组。相反，我们使用 Swift 对象来跟踪这些分割Range。最初，该范围覆盖整个数组0 ..< numbers.count。当我们分割数组时，范围变得越来越小。

注意：需要注意的一件事是，range.upperBound总是指向最后一个元素之外的一个。在示例中，范围是0..<19因为数组中有 19 个数字，所以range.lowerBound = 0和range.upperBound = 19。但在我们的数组中，最后一个元素位于索引 18，而不是 19，因为我们从 0 开始计数。在处理范围时请记住这一点：始终比最后一个元素的upperBound索引多 1。

单步执行示例

详细了解该算法的工作原理可能会很有用。

上面示例中的数组由 19 个数字组成，排序后如下所示：

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]

我们正在尝试确定该数字是否43在此数组中。

要将数组分成两半，我们需要知道中间对象的索引。这是由这一行决定的：

let midIndex \= range.lowerBound + (range.upperBound \- range.lowerBound) / 2

最初，范围有lowerBound = 0和upperBound = 19。填写这些值，我们发现midIndex是0 + (19 - 0)/2 = 19/2 = 9。实际上是这样9.5，但因为我们使用的是整数，所以答案是向下舍入的。

在下图中，*显示了中间的项目。正如您所看到的，每侧的项目数量相同，因此我们从中间分开。

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
                                  *

现在二分查找将决定使用哪一半。代码中的相关部分是：

if a\[midIndex\] \> key {
    // use left half
} else if a\[midIndex\] < key {
    // use right half
} else {
    return midIndex
}

在这种情况下，a[midIndex] = 29. 这小于搜索键，因此我们可以安全地得出结论：搜索键永远不会位于数组的左半部分。毕竟，左半部分只包含小于 的数字29。因此，搜索键必须位于右半部分的某个位置（或者根本不在数组中）。

现在我们可以简单地重复二分搜索，但在数组区间 frommidIndex + 1到range.upperBound：

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]

由于我们不再需要关心数组的左半部分，因此我用x's 对其进行了标记。从现在开始，我们将只查看从数组索引 10 开始的右半部分。

我们计算新的中间元素的索引：midIndex = 10 + (19 - 10)/2 = 14，并将数组再次从中间拆分。

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
                                                 *

正如您所看到的，a[14]确实是数组右半部分的中间元素。

搜索关键字大于还是小于a[14]？它更小，因为43 < 47. 这次我们取左半部分并忽略右侧较大的数字：

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]

新的midIndex在这里：

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]
                                     *

搜索关键字大于37，因此继续右侧：

[ x, x, x, x, x, x, x, x, x, x | x, x | 41, 43 | x, x, x, x, x ]
                                        *

同样，搜索键更大，因此再次分割并取右侧：

[ x, x, x, x, x, x, x, x, x, x | x, x | x | 43 | x, x, x, x, x ]
                                            *

现在我们完成了。搜索键等于我们正在查看的数组元素，因此我们终于找到了我们要搜索的内容： number43位于数组索引处13。哇！

这可能看起来工作量很大，但实际上只花了四个步骤就可以在数组中找到搜索键，这听起来很正确，因为log_2(19) = 4.23. 如果使用线性搜索，则需要 14 步。

如果我们搜索42而不是搜索会发生什么43？在这种情况下，我们无法进一步拆分数组。变得range.upperBound小于range.lowerBound。这告诉算法搜索键不在数组中并返回nil。

注意：二分搜索的许多实现都会计算midIndex = (lowerBound + upperBound) / 2。这包含一个仅在非常大的数组中出现的微妙错误，因为lowerBound + upperBound可能会溢出整数可以容纳的最大数量。这种情况在 64 位 CPU 上不太可能发生，但在 32 位机器上肯定会发生。

迭代与递归

二分查找本质上是递归的，因为您一遍又一遍地将相同的逻辑应用于越来越小的子数组。但是，这并不意味着您必须实现binarySearch()为递归函数。使用简单的循环而不是大量的递归函数调用将递归算法转换为迭代版本通常更有效。

下面是 Swift 中二分搜索的迭代实现：

func binarySearch<T: Comparable\>(\_ a: \[T\], key: T) \-> Int? {
    var lowerBound \= 0
    var upperBound \= a.count
    while lowerBound < upperBound {
        let midIndex \= lowerBound + (upperBound \- lowerBound) / 2
        if a\[midIndex\] \== key {
            return midIndex
        } else if a\[midIndex\] < key {
            lowerBound \= midIndex + 1
        } else {
            upperBound \= midIndex
        }
    }
    return nil
}

正如您所看到的，该代码与递归版本非常相似。主要区别在于循环的使用while。

像这样使用它：

let numbers \= \[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67\]

binarySearch(numbers, key: 43)  // gives 13

结束

数组必须先排序是不是有问题？这取决于。请记住，排序需要时间 - 二分搜索加排序的组合可能比简单的线性搜索慢。当您只排序一次然后进行多次搜索的情况下，二分搜索会发挥作用。

另请参阅维基百科。