【数据结构与算法 - Swift实现】11 - 二分查找 (Bi
2019-05-07 本文已影响0人
Lebron_James
二分查找是高效搜索算法中的一员，时间复杂度为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。
