iOS菜逼学算法(一)二分查找

最近忙着刷题之余,结合自己的一些demo体会到算法的重要性,优势

二分查找原理

我相信很多人都会用百度和Google,就不详细讲了。

二分,字面意思就是对半分找东西,一直这么下去。

例:

有10个数(0 - 9)顺序排列(二分查找的关键);左右区分


第一次二分

左边-> 0,1,2,3,4

右边-> 5,6,7,8,9

需要查找8的位置,10个数的中间就是5了,判断下是不是中间数;重点来了->比较查找数和中间数大小,就可以判断是在左还是右,结果再右边。


第二次二分

左边-> 5,6 (NO)

中间 =7(NO)

右边-> 8,9(YES)

按照第一次二分的原理,还是右边


第三次二分已经没啥必要了(怎么分?)

都写了相信的注释...

为啥结束位置-1?我们需要的是下标,不是个数

中间下标不要担心小数点...(脑壳短路的,直接百度,或者看下数组objectAtIndex)

这里有中文注释->看不懂打我啊

重点:判断左右....然后二分下标;没懂的多看几遍,还没懂的来打我。

说了一段原理,代码也上了,最后来个测试,不说百万级数据我们来个差不多的测试下


100000个数的查找时间对比

demo https://github.com/xiongq/binarySearch-demo.git

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容