Swift 算法实战之路:二分搜索

[中文教程]
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看95 回复回复1 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 95|回复: 1
收起左侧

[中文教程] Swift 算法实战之路:二分搜索

[复制链接]
代码买卖 发表于 2016-9-7 03:34:47 | 显示全部楼层 |阅读模式
快来登录
获取最新的苹果动态资讯
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
本帖最后由 代码买卖 于 2016-9-7 05:09 编辑

紧接上文,排序之后我们来谈谈搜索。一般最直接的搜索就是遍历集合,然后找到满足条件的元素。这种直接的暴力搜索法实现起来简单,但是当输入数据十分巨大的时候,搜索起来就会很慢(复杂度O(n))。本文将探讨算法复杂度更低、效果更好的搜索方法 —— 二分搜索。本文的主要内容为:

  • 基本概念
  • 实战演练
  • iOS中搜索与排序的配合使用


Swift 算法实战之路:二分搜索 0

Swift 算法实战之路:二分搜索 - 敏捷大拇指 - Swift 算法实战之路:二分搜索 0





1、基本概念

二分搜索,即在有序数组中,查找某一特定元素的搜索。它从中间的元素开始,如果中间的元素是要找的元素,则返回;若中间元素小于要找的元素,则要找的元素一定在大于中间元素的那一部分,那只需搜索那部分即可;反之搜索小于中间元素的部分即可。重复以上步骤,直到找到或确认该元素不存在为止。这样每一次搜索,就能减小一办的搜索范围,所以它的算法复杂度为O(logn)

Swift 实现二分搜索:

[Swift] 纯文本查看 复制代码
// 假设nums是一个升序数组
func binarySearch(nums: [Int], target: Int) -> Bool {
  var left = 0
  var right = nums.count - 1
  var mid = 0

  while left <= right {
    mid = (right - left) / 2 + left

    if nums[mid] == target {
      return true
    } else if nums[mid] < target {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return false
}


这里要注意两个细节:

第一,mid 定义在 while 循环外面,如果定义在里面,则每次循环都要重新给 mid 分配内存空间,造成不必要的浪费;定义在循环之外,每次循环只是重新赋值;

第二,每次重新给 mid 赋值不能写成mid = (right + left) / 2。这种写法表面上看没有问题,但当数组的长度非常大、算法又已经搜索到了最右边部分的时候,那么right + left就会非常之大,造成溢出导致程序崩溃。所以解决问题的办法是写成 mid = (right - left) / 2 + left。

当然,我们可以用递归来实现二分搜索:

[Swift] 纯文本查看 复制代码
func binarySearch(nums: [Int], target: Int) -> Bool {
  return binarySearch(nums: nums, target: target, left: 0, right: nums.count - 1)
}

func binarySearch(nums: [Int], target: Int, left: Int, right: Int) -> Bool {
  guard left <= right else {
    return false
  }

  let mid = (right - left) / 2 + left

  if nums[mid] == target {
    return true
  } else if nums[mid] < target {
    return binarySearch(nums: nums, target: target, left: mid + 1, right: right)
  } else {
    return binarySearch(nums: nums, target: target, left: left, right: mid - 1)
  }
}





2、实战演练



2.1、第一题:版本崩溃

上面的二分搜索基本上稍微有点基本功的都能写出来。所以,真正面试的时候,最多也就是问问概念,不会真正让你实现的。真正的面试题,长下面这个样子:

有一个产品发布了n个版本。它遵循以下规律:假如某个版本崩溃了,后面的所有版本都会崩溃。

举个例子:一个产品假如有5个版本,1,2,3版都是好的,但是第4版崩溃了,那么第5个版本(最新版本)一定也崩溃。第4版则被称为第一个崩溃的版本。

现在已知一个产品有n个版本,而且有一个检测算法 func isBadVersion(version: Int) -> Bool 可以判断一个版本是否崩溃。假设这个产品的最新版本崩溃了,求第一个崩溃的版本。

分析这种题目,同样还是先抽象化。我们可以认为所有版本为一个数组[1, 2, 3, ..., n],现在我们就是要在这个数组中检测出满足 isBadVersion(version) == true中version的最小值。

很容易就想到二分搜索,假如中间的版本是好的,第一个崩溃的版本就在右边,否则就在左边。我们来看一下如何实现:

[Swift] 纯文本查看 复制代码
func findFirstBadVersion(version: n) -> Int {
  // 处理特殊情况
  guard n >= 1 else {
    return -1
  }

  var left = 1
  var right = n
  var mid = 0

  while left < right {
    mid = (right - left) / 2 + left
    if isBadVersion(mid) {
      right = mid
    } else {
      left = mid + 1
    }
  }

  return left    // return right 同样正确
}


这个实现方法要注意两点:

  • 当发现中间版本(mid)是崩溃版本的时候,只能说明第一个崩溃的版本小于等于中间版本。所以只能写成 right = mid
  • 当检测到剩下一个版本的时候,我们已经无需在检测直接返回即可,因为它肯定是崩溃的版本。所以while循环不用写成left <= right




2.2、第二题:搜索旋转有序数组

上面的题目是一个简单的二分搜索变种。我们来看一个复杂版本的:

一个有序数组可能在某个位置被旋转。给定一个目标值,查找并返回这个元素在数组中的位置,如果不存在,返回-1。假设数组中没有重复值。

举个例子:[0, 1, 2, 4, 5, 6, 7]在4这个数字位置上被旋转后变为[4, 5, 6, 7, 0, 1, 2]。搜索4返回0。搜索8则返回-1。

假如这个有序数组没有被旋转,那很简单,我们直接采用二分搜索就可以解决。现在被旋转了,还可以采用二分搜索吗?

我们先来想一下旋转之后的情况。第一种情况是旋转点选的特别前,这样旋转之后左半部分就是有序的;第二种情况是旋转点选的特别后,这样旋转之后右半部分就是有序的。如下图:

Swift 算法实战之路:二分搜索 1

Swift 算法实战之路:二分搜索 - 敏捷大拇指 - Swift 算法实战之路:二分搜索 1


那么怎么判断是结果1还是结果2呢?我们可以选取整个数组中间元素(mid) ,与数组的第1个元素(left)进行比较 —— 如果 mid > left,则是旋转结果1,那么数组的左半部分就是有序数组,我们可以在左半部分进行正常的二分搜索;反之则是结果二,数组的右半部分为有序数组,我们可以在右半部分进行二分搜索。

这里要注意一点,即使我们一开始清楚了旋转结果,也要判断一下目标值所落的区间。对于旋转结果1,数组左边最大的值是mid,最小值是left。假如要找的值target落在这个区间内,则使用二分搜索。否则就要在右边的范围内搜索,这个时候相当于回到了一开始的状态,有一个旋转的有序数组,只不过我们已经剔除了一半的搜索范围。对于旋转结果2,也类似处理。全部代码如下:

[Swift] 纯文本查看 复制代码
func search(nums: [Int], target: Int) -> Int {
  var left = 0
  var right = nums.count - 1
  var mid = 0

  while left <= right {
    mid = (right - left) / 2 + left

    if nums[mid] == target {
      return mid
    }

    if nums[mid] >= nums[left] {
      if nums[mid] > target && target >= nums[left] {
        right = mid - 1
      } else {
        left = mid + 1
      }
    } else {
      if nums[mid] < target && target <= nums[right] {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
  }

  return -1
}


大家可以想一下假如旋转后的数组中有重复值比如[3,4,5,3,3,3]该怎么处理?




3、iOS中搜索与排序的配合使用

Swift 算法实战之路:二分搜索 2

Swift 算法实战之路:二分搜索 - 敏捷大拇指 - Swift 算法实战之路:二分搜索 2

RSS Reader

上图是iOS中开发的一个经典案例:新闻聚合阅读器(RSS Reader)。因为新闻内容经常会更新,所以每次下拉刷新这个UITableView或是点击右上角刷新按钮,经常会有新的内容加入到原来的dataSource中。刷新后合理插入新闻,就要运用到搜索和排列。

笔者在这里提供一个方法。首先,写一个ArrayExtensions.swift;

[Swift] 纯文本查看 复制代码
extension Array {
  func indexForInsertingObject(object: AnyObject, compare: ((a: AnyObject, b: AnyObject) -> Int)) -> Int {
    var left = 0
    var right = self.count
    var mid = 0

    while left < right {
      mid = (right - left) / 2 + left

      if compare(a: self[mid] as! AnyObject, b: object) < 0 {
        left = mid + 1
      } else {
        right = mid
      }
    }

    return left
  }
}


然后在FeedsViewController(就是显示所有新闻的tableView的controller)里面使用这个方法。一般情况下,FeedsViewController里面会有一个dataSource,比如一个装新闻的array。这个时候,我们调用这个方法,并且让它每次都按照新闻的时间进行排序

[Swift] 纯文本查看 复制代码
let insertIdx = news.indexForInsertingObject(object: singleNews) { (a, b) -> Int in
  let newsA = a as! News
  let newsB = b as! News
  return newsA.compareDate(newsB)
}

news.insert(singleNews, at: insertIdx)


这里你需要在News这个model里实现compareDate这个函数。




4、总结

二分搜索是一种十分巧妙的搜索方法,它的复杂度是主流算法中最低的。正以为其十分高效,它会经常配合排序出现在各种日常coding和iOS开发中。当然,二分搜索也会出现各种各样的变种,其实万变不离其宗,关键是想方法每次减小一半的搜索范围即可。

接下来一篇我们讨论Swift深度和广度优先搜索




相关内容

Swift 算法实战之路:基本语法与技巧

Swift 算法实战之路:数组,字符串,集合,与字典

Swift 算法实战之路:链表

Swift 算法实战之路:栈和队列

Swift 算法实战之路:二叉树

Swift 算法实战之路:排序

Swift 算法实战之路:二分搜索

Swift 算法实战之路:深度和广度优先搜索

Swift 算法实战之路:动态规划




作者:故胤道长

都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

本帖被以下淘专辑推荐:

swifter 发表于 2016-9-11 15:31:23 | 显示全部楼层
经典~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表