二分查找

2018-07-17  本文已影响39人  继续向前冲

目标：快速在数组中找到一个元素。

假设您有一个数组，并且您想确定某个特定数字是否在该数组中，如果是，那么返回索引。

在大多数情况下，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。对于数十亿个元素的数组，它只需要30个步骤。（然后再一次，你最后一次使用数十亿项目的数组是什么时候？）

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

以下是二分查找的工作原理：

现在你知道它为什么称为“二分”查找：在每一步中，它将数组分成两半。这个分而治之的过程就是让它能够快速缩小搜索关键字的位置。

代码

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

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
        
        // 选取点数据与key作比较key大将中间点设为范围最大值
        if a[midIndex] > key {
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
            
            // 选取点与key作比较如果中间点小于范围把中间点值设为范围最小值
        } else if a[midIndex] < key {
            return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
            
            // 找到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

NSInteger binarySearch(NSArray *array, NSInteger target) {
    if (!array.count) {
        return -1;//数组无元素,返回-1;
    }
    
    int low = 0;//数组起始元素下标
    unsigned long high = array.count - 1;//数组最后元素的下标
    
    while (low <= high) {
        //会有一些朋友看到有些人是( low + high ) / 2这样写的,但是这样写有一点不好,就是low+high会出现整数溢出的情况,如果存在溢出,你再除以2也是没有用的,所以不能这么写
        unsigned long mid = low + ((high - low)/2);
        
        //第mid项的内容
        NSNumber * num = [array objectAtIndex:mid];
        
        if (target == num.integerValue) {
            return low;
        }else if (num.integerValue > target){
            high = mid - 1;//左边进行查找
        }else{
            low = mid +1;//右边进行查找
        }
    }
    return -1;//数组中不存该数,返回-1;
    

    
}

请注意numbers数组已排序。二分查找算法不起作用！

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

注意：要注意的一点是，range.upperBound总是指出一个超出最后一个元素。在这个例子中，范围是0..<19因为数组中有19个数字，所以range.lowerBound = 0和range.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 = 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。因此，搜索键必须位于某处的右半部分（或者根本不在该阵列中）。

现在我们可以简单地重复二分搜索，但是从数组间隔midIndex + 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 ]
                                            *

现在我们完成了。搜索关键字等于我们正在查看的数组元素，所以我们终于找到了我们正在搜索的内容：number 43是数组索引13。w00t！

它可能看起来像很多工作，但实际上它只需要四个步骤来找到数组中的搜索关键字，这听起来是正确的，因为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

结束

这是一个问题，数组必须先排序？这取决于。请记住，排序需要时间 - 二分查找加排序的组合可能比进行简单的线性搜索要慢。二分查找会在您仅排序一次然后执行多次搜索的情况下发光。

上一篇下一篇

猜你喜欢

热点阅读