Swift算法－二分搜索Binary Search

声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流

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

假如你有一个数组，包含数百个数字，然后你需要从中找出某一个数字所在的位置，在大多数情况下，Swift自带的indexOf()函数可以快速帮你解决这种问题。过程如下：

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

numbers.indexOf(43)  // returns 15

Swift自带的 indexOf函数是属于线性搜索，其代码为：

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

虽然很简便，但是由于是线性搜索，意味着我们需要从数组的第一位开始搜索整个数组，在最糟糕的情况下，可能你需要搜寻完整个数组才发现数组里面没有你需要寻找的数字。所以说，线性搜索算法跟数组的大小相关性很大，数组越大，意味着消耗的时间越久。

分治法

对于数组大的情况下，最经典的算法当属二分搜索算法。它的核心就是不断的将数组一分为二，直到找到我们寻找的数字。

比如说，一个大小为n的数组，使用线性搜索算法的效率为O(n)，而二分搜索算法的效率为O(log n)。更详细一点来说，当数组大小为1000000的时候，二分搜索算法只花了20步就能找到结果。因为log_2(1000000) = 19.9。而当数组大小上升到十亿级别的时候，二分搜索却只需要30步就能找到答案。

不过，使用二分搜索必须有个前提：这个必须数组是按照一定顺序排列的。

二分搜索的工作原理：

1.将数组一分为二，并决定你需要寻找的元素是在数组的左边还是右边。
2.由于我们的数组是已经排序好的数组，所以你只需要将寻找的元素和得到中间数字进行大小比较。
3.确定好寻找的元素在哪边后，在新的数组里面继续一分为二，然后比较大小。
4.不断重复上述过程，直到我们找到这个元素在数组中的位置，或者当数组无法继续一分为二的时候，判断数组中不存在需要寻找的元素。

代码

以下为递归版的二分搜索算法：

func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
    if range.lowerBound >= range.upperBound {
        // 如果我们进入这个函数，则说明要寻找的元素不在数组里
        return nil

    } else {
        // 计算数组一分为二的位置
        let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

        // 判断寻找的元素是否在数组左侧
        if a[midIndex] > key {
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)

        // 判断寻找的元素是否在数组右侧
        } else if a[midIndex] < key {
            return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)

        // 如果进入这个函数内部，则说明我们已经在数组里找到这个元素！
        } else {
            return midIndex
        }
    }
}

我们可以在playground里进行测试：

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)  // 得到 13

必须注意这里的numbers是已经排序好的！

虽然说二分算法是不断的进行数组拆分，但是这里我们并不是真的去创建两个新的数组，而是使用Swfit中的Range对象。最初的时候，range包含数组的所有元素的位置，0..<numbers.count，随着拆分不断进行，range越变越小。

示例解析

我们有一组已经排序好的数组：

[ 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 = 9.5 = 9（向下取整）。如图，我们的中间数组为29，其左右两个数组位数大小相等。

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

接下来，二分算法将会决定我们接下去会使用哪一边的数组。相关代码为：

if a[midIndex] > key {
    // 使用左边部分
} else if a[midIndex] < key {
    // 使用右边部分
} else {
    return midIndex
}

由于29比43小，所以我们可以确定左侧的数组不存在43。我们继续在右侧数组中寻找43。此时新的范围为midIndex + 1 到range.upperBound。

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

此时新的中间值为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 ]
                                                 *

新的中间值对应的数字为47<43，所以我们继续在左侧数组进行拆分。

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

此时新的中间值为：

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

37<43。在右侧数组继续拆分：

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

再一次，41<43，继续拆分：

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

终于，我们找到了43，此时的中间值为13，即43在数组的位置为13。整个过程看起来好像很冗长，但其实我们只花了4个步骤就得到了答案。与log_2(19) = 4.23相近。而如果是线性搜索，我们需要花14个步骤才能找到43！

迭代vs递归

通常情况下二分搜索属于递归过程，因为不断运用了同样的逻辑去缩小数组。但是这不意味着我们不能使用迭代的方法去实现二分搜索。同时，递归算法转化成迭代算法实现通常会提高运行效率，因为它只用了一个循环而不是多个嵌套循环。

以下为迭代版本的二分搜索算法：

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循环的使用。我们同样可以在playground对代码进行测试:

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)  // 得到13

结语

看到这里，是否会感觉需要将数组先进行排序会很复杂？其实不然，虽然排序也需要花时间，但是，排序加上二分搜索的过程往往会比直接进行线性查找来得更快速。 特别是当你不是单单只想寻找一个元素的情况下。