锐客网

  1. 首页 > it技术 > >

【数据结构与算法|【数据结构与算法 - Swift实现】11 - 二分查找 (Binary Search)

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

  • 集合中的元素必须可以使用索引直接访问，在 Swift 中，这个集合必须是RandomAccessCollection类型。
  • 集合中的元素必须是有序的
实现
假设要查找的元素为 A，集合从小到大的顺序排列，二分查找的步骤如下：
  • 首先找到中间元素
  • 拿 A 与中间元素对比，如果 A 等于中间元素，直接返回索引，否则继续下列步骤
  • 如果 A 小于中间元素，则用所有左边元素组成的集合进行递归；如果 A 大于中间元素，则用所有有边元素组成的集合进行递归
实现代码如下：
extension RandomAccessCollection where Element: Comparable { func binarySearch(for value: Element, in range: Range? = nil) -> Index? {let range = range ?? startIndex..

代码解析：
  • 上面已经提到，要使用二分法的必须是 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实现】11 - 二分查找 (Binary Search)】欢迎加入我管理的Swift开发群：536353151。
下一篇文章：【数据结构与算法 - Swift实现】12 - 时间复杂度为O(n^2)的排序算法

    推荐阅读


    上一篇：酒泉中学2017-2018学年度第二学期高一年级期中考试总结

    下一篇：Unity使用Cinemachine和Timeline入门