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

111721232-e8e8069e07e22728

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

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

基本概念

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

Swift 实现二分搜索

这里要注意两个细节:

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

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

实战演练

第一题:版本崩溃

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

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

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

这个实现方法要注意两点

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

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

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

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

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

121721232-b6cf3ce7baa074b6

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

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

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

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

131721232-460e500fbe994d6a

RSS Reader

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

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

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

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

总结

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

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

1 收藏 评论

关于作者:故胤道长

Uber 硅谷总部iOS工程师,负责iOS端架构和工具的开发。卡内基美隆大学电子计算机工程硕士毕业。 个人主页 · 我的文章 · 3 ·  

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部