【数据结构与算法 - Swift实现】11 - 二分查找 (Bi

二分查找是高效搜索算法中的一员，时间复杂度为O(log n)。使用搜索算法前，需要满足两个条件：

• 集合中的元素必须可以使用索引直接访问，在 Swift 中，这个集合必须是RandomAccessCollection类型。
• 集合中的元素必须是有序的

实现

假设要查找的元素为 A，集合从小到大的顺序排列，二分查找的步骤如下：

• 首先找到中间元素
• 拿 A 与中间元素对比，如果 A 等于中间元素，直接返回索引，否则继续下列步骤
• 如果 A 小于中间元素，则用所有左边元素组成的集合进行递归；如果 A 大于中间元素，则用所有有边元素组成的集合进行递归

实现代码如下：

extension RandomAccessCollection where Element: Comparable {
    func binarySearch(for value: Element,
                      in range: Range<Index>? = nil) -> Index? {
        
        let range = range ?? startIndex..<endIndex
        guard range.lowerBound < range.upperBound else { return nil }
        
        let size = distance(from: range.lowerBound, to: range.upperBound)
        let middle = index(range.lowerBound, offsetBy: size / 2)
        let middleValue = self[middle]
        
        if middleValue == value {
            return middle
            
        } else if value < middleValue {
            return binarySearch(for: value, in: range.lowerBound..<middle)
            
        } else {
            return binarySearch(for: value, in: middle..<range.upperBound)
        }
    }
}

代码解析：

• 上面已经提到，要使用二分法的必须是 RandomAccessCollection 类型，所以我们通过扩展这个协议来实现二分查找，并且 Element 必须是 Comparable
• 因为我们要使用递归，所以方法中需要 range 参数
• 定义 range 变量，如果 range 为空，则默认是原来数组的整个范围
• 判断传入的范围中，是否包含至少一个元素，如果不包含直接返回 nil
• 读取中间元素的值
• 中间元素和要查找的值进行对比，如果相等，直接返回中间索引；如果要查找的值小于中间元素，用左边的范围继续查找；如果要查找的值大于中间元素，用右边的范围继续查找

测试如下：

let array = [0, 9, 13, 20, 21, 25, 35, 120, 250]

let indexOf = array.index(of: 20)
let binarySearchFor = array.binarySearch(for: 20)

print("index(of:): \(String(describing: indexOf))")
print("binarySearch(for:): \(String(describing: binarySearchFor))")

// 结果
index(of:): Optional(3)
binarySearch(for:): Optional(3)

完整代码 >>

参考资料

Data Structures and Algorithms in Swift --- raywenderlich.com，如果想看原版书籍，请点击链接购买。

完

欢迎加入我管理的Swift开发群：536353151。

下一篇文章：【数据结构与算法 - Swift实现】12 - 时间复杂度为O(n^2)的排序算法