今天主要跟大家分享二分查找算法。
有兴趣的朋友的可以去阅读《算法图解》这本书。
首先说下什么是算法。
算法定义：
一组完成任务的指令。任何的代码片段都可视为算法。
算法的优缺点：
不同的算法，性能高低不同。
算法的作用：
解决问题的技巧。不同的问题，可以选择不同解决方式。
二分查找法：
定义:在一个有序的元素列表中，查找元素是否包含在列表，或者是具体在某个索引位置。
EX:
例如我们要在100个有序的数组中，找到40这个数，那么在数组的哪个位置呢？
笨方法:一个挨着一个的找。找100次就找到了。
好方法：折半查找,首先找出整个数组中的中位数和要查找的数，做比较。
分为两堆，一堆大数，一堆小数。如果中间数<查找数，那么就从大数堆里去找。
再把大数堆分为两堆，以此类推。就最终能到找到，你要找的数。
图片来自《算法图解》
代码如下：
说到算法，接下来就得说下“大O表示法”。
大O表示法 是一种特殊的表示法，指出了算法的速度有多快。
之前提到笨方法，就是线性时间 O(n) , n:表示操作数。
二分查找法，就是对数时间 O(logn)。查找100个数的数组，最多只要7次。
(log^100,log指的是log2,log2^100相当于问“将多少个2相乘的结果为100”)
如果忘了对数是什么？请自行百度一下。由于不是这次主要内容，这里就不展开介绍。
今天，就给大家分享到这。明天会继续分享《选择排序+数组和链表》。
PS:
如果你阅读之后，有所收获。请记得点赞哦。o(*￣︶￣*)o。你的支持将是我写作的动力。
