最近忙着刷题之余,结合自己的一些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)
按照第一次二分的原理,还是右边
第三次二分已经没啥必要了(怎么分?)
都写了相信的注释...
中间下标不要担心小数点...(脑壳短路的,直接百度,或者看下数组objectAtIndex)
重点:判断左右....然后二分下标;没懂的多看几遍,还没懂的来打我。
说了一段原理,代码也上了,最后来个测试,不说百万级数据我们来个差不多的测试下