美文网首页swiftIOSiOS学习笔记
【译】Swift算法俱乐部-二分搜索

【译】Swift算法俱乐部-二分搜索

作者: Andy_Ron | 来源:发表于2018-09-19 19:42 被阅读22次

    本文是对 Swift Algorithm Club 翻译的一篇文章。
    Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
    🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。欢迎有兴趣学习算法和数据结构,有时间的小伙伴一起参与翻译,欢迎issue,或者直接提交pull request。
    本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Binary Search


    Binary Search

    目标:在数组中快速寻找一个元素。

    假设你有一个数字数组,你想确定一个特定的数字是否在该数组中,如果在,那么获得这个数字的索引。

    对于上面的情况,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
    

    内置的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
    

    有什么问题呢? linearSearch()从头开始遍历整个数组,直到找到你正在寻找的元素。 在最坏的情况是数值不在数组中,那么之前的遍历就白费。

    平均而言,线性搜索算法需要查看数组中一半的值。 如果您的数组足够大,这将会变得非常慢!

    分而治之

    提升速度的经典方法是使用 二分搜索。 诀窍是将数组分成两半,直到找到值。

    对于大小为n的数组,性能不是线性搜索的O(n),而是只有 O(log n)。换句话说,对具有1,000,000个元素的数组进行二分搜索只需要大约20个步骤来查找要查找的内容,因为log_2(1,000,000)= 19.9。对于具有十亿个元素的数组,它只需要30步。 (然而,你上一次使用数十亿项的数组是什么时候?)

    听起来很棒,但使用二分搜索有一个缺点:数组必须被排好序的。 在实践中,这通常不是问题。

    下面二分搜索的工作原理:

    • 将数组分成两半,并确定您要查找的内容(称为搜索键)是在左半部分还是在右半部分。
    • 您如何确定搜索键的键在哪一半呢? 这就是首先要对数组进行排序的原因,排好序你就可以做一个简单的<>比较。
    • 如果搜索键位于左半部分,则在那里重复该过程:将左半部分分成两个更小的部分,并查看搜索键位于哪一块。 (同样,对于右半部分同样处理。)
    • 重复此操作直到找到搜索键。 如果无法进一步拆分数组,则必须遗憾地得出结论,搜索键不在数组中。

    现在你知道为什么它被称为“二分”搜索:在每一步中它将数组分成两半。 分而治之 可以快速缩小搜索键所在的位置。

    代码

    这是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
            }
        }
    }
    

    尝试一下,将代码复制到 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)  // gives 13
    

    请注意,numbers数组已排序。 否则二分搜索算法不能工作!

    二分搜索通过将数组分成两半来搜索,但我们实际上并没有创建两个新数组。 我们使用SwiftRange对象跟踪这些拆分。起初,此范围涵盖整个数组,0 .. <numbers.count。 当我们拆分数组时,范围变得越来越小。

    注意: 需要注意的一点是range.upperBound总是指向最后一个元素之后的元素。 在这个例子中,范围是0 .. <19,因为数组中有19个数字,所以range.lowerBound = 0range.upperBound = 19。但是在我们的数组中,最后一个元素是在索引18而不是19,因为我们从0开始计数。在处理范围时要记住这一点:upperBound总是比最后一个元素的索引多一。

    分步执行示例

    查看算法的详细工作方式或许是很有用的。

    上例中的数组由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 = 0upperBound = 19。 细看,我们发现midIndex0 +(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的数字。 因此,搜索键肯定位于右半部分(或根本不在数组中)。

    现在我们可以简单地重复二分搜索,数组间距从midIndex + 1range.upperBound

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

    由于我们不再需要关注数组的左半部分,我用x标记了它。 从现在开始,我们只看右半部分,从数组索引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 ]
                                                *
    

    现在我们已经完成了。搜索键等于我们正在查看的数组元素,所以我们终于找到了我们要搜索的内容:数字43位于数组索引13

    这可能看起来像很多工作,但实际上只需要四个步骤就能找到数组中的搜索键,因为log_2(19)= 4.23。通过线性搜索,它将花费14个步骤。

    如果我们要搜索42而不是43会发生什么?在这种情况下,最后我们不能再进一步拆分数组。 range.upperBound变得小于range.lowerBound。这告诉算法搜索键不在数组中,它返回nil

    注意: 二分搜索许多执行会计算 midIndex = (lowerBound + upperBound) / 2。这包含了一个在非常大的数组中会出现的细微bug,因为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
    

    结束

    数组必须先排序是一个问题? 排序是需要时间的 —— 二分搜索和排序的组合可能比进行简单的线性搜索要慢。但是在您只排序一次然后进行多次搜索的情况下,二分搜索会起到大作用。

    二分搜索的维基百科

    作者:Matthijs Hollemans
    翻译:Andy Ron
    校对:Andy Ron

    相关文章

      网友评论

        本文标题:【译】Swift算法俱乐部-二分搜索

        本文链接:https://www.haomeiwen.com/subject/gohbnftx.html