iOS开发中使用算法之二分搜索算法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/69021838

本人是一名iOS开发程序猿,说实话在之前的开发项目中并没有到多少算法,算法对于本人也可以说是个硬伤。最近在找工作,面试官就会提到一些算法,由于不常用算法也就很难很好地回答面试的问题。由于之前学习过C以及数据结构现在再看看一些常用算法还是能很快理解并掌握的,下面就说说常用的搜索算法--二分搜索算法。

为什么要使用算法?

(个人愚见:iOS客户端开始主要是展示界面,将一些数据以界面的方式展示给用户,至于一些数据的处理已经在后台处理过了,我们是直接获取后台的数据的,而且OC是面向对象的,好多算法的东西也已经被某些方法封装了,如:在数组中插入某个位置插入一个元素,所以个人感觉iOS开发中使用算法的场景很少。当然这只是个人愚见,而且很可能被某些大神批判、不屑,而且这种想法很有可能被未来某天的自己所鄙视,但这种想法是现在的我的真实想法。)

使用算法是为了提高开发效率,突然想到之前看到的一副动态图,动态图分为两部分,上部分是一条狗叼着一根木棍往门里冲,可木棍的长度长于门的宽度,导致狗始终无法通过门,而且狗还在一直横冲直撞。下部分同样是一条狗叼着一根木棍往门里冲,可当狗发现木棍的长度长于门的宽度的时候,狗进行了几秒的“思考”,然后把脖子一歪,木棍也随然斜了,正好能让狗通过门。动态图的标题是“不会算法的程序员和会算法的程序员的区别”。动态图很搞笑,可揭露的问题却很深刻。不会算法的程序猿只会蛮干一起,最后可能也无法实现目的,即时实现了也算是暴力实现,效率并不怎么高,而这就是我们要学习使用算法的原因。

在没使用算法之前时间复杂度是O(N),而在使用算法之后,时间复杂度就变成了O(logN),大大节省了时间,提高了开发效率。

二分搜索使用的前提是搜索的数据是有序的,如:升序。当然如果数据是无序的我们也可以先利用冒泡算法将无序的数据变成有序的数据,然后再利用二分搜索法进行搜索。

二分搜索的思路:首先我们需要获取三个值,分别是第一个数据、最后一个数据、中间数据。然后我们需要进行数据的比较,先比较中间值是否等于我们的目标值,如果中间值大于我们的目标值,我们则将中间值做为最后一个数据,如果中间值小于我们的目标值,我们则将中间值做为第一个数据,这样就出现了一串新的有序的数据,然后再比较目标值是否等于第一值和最后一个值,就这样进行循环,直到在搜索数据中找到目标值。

OC代码:

// 在某个数组中搜索目标

- (NSInteger)binarySearchTarget:(NSInteger)target inArray:(NSArray *)arr{

if (arr.count <1) {

return -1;

    }

// 定义三个变量第一个值下标、中间值下标、最后一个值下标

NSInteger start =0;

NSInteger end = arr.count -1;

NSInteger mind =0;

// 进行循环

while (start < end -1) {   // 数组中第一个对象和最后一个对象之前还有其他对象则进行循环

        mind = start + (end - start) / 2;   // (start + end) / 2;

if ([arr[mind]integerValue]> target) {// 如果中间值大于目标值

            end = mind; // 中间值做为最后一个值,在前半段再进行相同的搜索

        }else{

            start = mind;

        }

    }

if ([arr[start]integerValue] == target) { // 如果第一个值和目标值相等则获取第一个值的下标

return start;

    }

if ([arr[end]integerValue] == target) {   // 如果最后一个值和目标值想等则获取最后一个下标

return end;

    }

return -1;

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

博弈论进阶之SG函数

SG函数 个人理解:SG函数是人们在研究博弈论的道路上迈出的重要一步,它把许多杂乱无章的博弈游戏通过某种规则结合在了一起,使得一类普遍的博弈问题得到了解决。 从...

42450
来自专栏钱塘大数据

风靡全球的15则数学动图,让你秒懂数学概念

首先,把圆解剖为一个三角形。底边是周长。然后根据三角形的面积推出圆的面积,so easy~

11730
来自专栏大数据文摘

Reading Club | 算法和人生选择:如何给洗好的袜子排序呢?

14230
来自专栏ACM算法日常

5行位运算,map靠边站——位操作进阶

Given an array of integers, every element appears three times except for one. F...

13210
来自专栏专知

【Code】关关的刷题日记22——Leetcode 53. Maximum Subarray

关小刷刷题 22——Leetcode 53. Maximum Subarray 题目 Find the contiguous subarray within a...

30870
来自专栏我和未来有约会

[Silverlight动画]转向行为 - 群落

说到群落,很难不引用Craig Reynolds和他的"boilds"模拟系统。Reynolds很牛的将一个看似非常恐怖的复杂过程,拆成了几个比较简单的行为。 ...

22780
来自专栏大数据文摘

手把手 | 用StackOverflow访问数据实现主成分分析(PCA)

15870
来自专栏新智元

邓侃:谷歌Talk to books引爆搜索方式革命

?---- 【新智元导读】昨天,新智元介绍了谷歌的全新搜索工具“Talk to Books”,基于自然语言文本理解,用户能够凭语义而非关键词来实现搜索功能。谷歌...

29660
来自专栏闪电gogogo的专栏

P问题、NP问题、NPC问题

   看师兄们的论文经常说一句这是个NP难问题,所以采用另外一种方法来代替(比如凸松弛,把l0范数的问题松弛为l1范数的问题来求解)。然后搜索了相关知识,也还是...

39160
来自专栏C语言及其他语言

【每日一题】问题 1429[蓝桥杯][历届试题]兰顿蚂蚁

题目描述 ? 兰顿蚂蚁,是于1986年,由克里斯·兰顿提出来的,属于细胞自动机的一种。 平面上的正方形格子被填上黑色或白色。在其中一格正方形内有...

29660

扫码关注云+社区

领取腾讯云代金券