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

1,311 阅读7分钟
原文链接: www.jianshu.com

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

基本概念

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

Swift 实现二分搜索

// 假设nums是一个升序数组
func binarySearch(nums: [Int], target: Int) -> Bool {
  var left = 0
  var right = nums.count - 1
  var mid = 0

  while left <= 1="" 2="" right="" {="" mid="(right" -="" left)="" +="" left="" if="" nums[mid]="=" target="" return="" true="" }="" else="" <="" false="" }<="" code="">

这里要注意两个细节:

第一,mid 定义在 while 循环外面,如果定义在里面,则每次循环都要重新给 mid 分配内存空间,造成不必要的浪费;定义在循环之外,每次循环只是重新赋值;
第二,每次重新给 mid 赋值不能写成mid = (right + left) / 2。这种写法表面上看没有问题,但当数组的长度非常大、算法又已经搜索到了最右边部分的时候,那么right + left就会非常之大,造成溢出导致程序崩溃。所以解决问题的办法是写成 mid = (right - left) / 2 + left

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

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 <= 2="" right="" else="" {="" return="" false="" }="" let="" mid="(right" -="" left)="" +="" left="" if="" nums[mid]="=" target="" true="" <="" binarysearch(nums:="" nums,="" target:="" target,="" left:="" 1,="" right:="" right)="" left,="" 1)="" }<="" code="">

实战演练

第一题:版本崩溃

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

有一个产品发布了n个版本。它遵循以下规律:假如某个版本崩溃了,后面的所有版本都会崩溃。
举个例子:一个产品假如有5个版本,1,2,3版都是好的,但是第4版崩溃了,那么第5个版本(最新版本)一定也崩溃。第4版则被称为第一个崩溃的版本。
现在已知一个产品有n个版本,而且有一个检测算法 func isBadVersion(version: Int) -> Bool 可以判断一个版本是否崩溃。假设这个产品的最新版本崩溃了,求第一个崩溃的版本。

分析这种题目,同样还是先抽象化。我们可以认为所有版本为一个数组[1, 2, 3, ..., n],现在我们就是要在这个数组中检测出满足 isBadVersion(version) == true中version的最小值。
很容易就想到二分搜索,假如中间的版本是好的,第一个崩溃的版本就在右边,否则就在左边。我们来看一下如何实现:

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 同样正确
}

这个实现方法要注意两点

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

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

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

一个有序数组可能在某个位置被旋转。给定一个目标值,查找并返回这个元素在数组中的位置,如果不存在,返回-1。假设数组中没有重复值。
举个例子:[0, 1, 2, 4, 5, 6, 7]在4这个数字位置上被旋转后变为[4, 5, 6, 7, 0, 1, 2]。搜索4返回0。搜索8则返回-1。

假如这个有序数组没有被旋转,那很简单,我们直接采用二分搜索就可以解决。现在被旋转了,还可以采用二分搜索吗?
我们先来想一下旋转之后的情况。第一种情况是旋转点选的特别前,这样旋转之后左半部分就是有序的;第二种情况是旋转点选的特别后,这样旋转之后右半部分就是有序的。如下图:


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

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

func search(nums: [Int], target: Int) -> Int {
  var left = 0
  var right = nums.count - 1
  var mid = 0

  while left <= 2="" right="" {="" mid="(right" -="" left)="" +="" left="" if="" nums[mid]="=" target="" return="" }="">= nums[left] {
      if nums[mid] > target && target >= nums[left] {
        right = mid - 1
      } else {
        left = mid + 1
      }
    } else {
      if nums[mid] < target && target <= 1="" nums[right]="" {="" left="mid" +="" }="" else="" right="mid" -="" return="" -1="" }<="" code="">

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

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


RSS Reader

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

笔者在这里提供一个方法。首先,写一个ArrayExtensions.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。这个时候,我们调用这个方法,并且让它每次都按照新闻的时间进行排序

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这个函数。

总结

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