算法图解一（二分查找）

今天主要跟大家分享二分查找算法。

有兴趣的朋友的可以去阅读《算法图解》这本书。

首先说下什么是算法。

算法定义：

一组完成任务的指令。任何的代码片段都可视为算法。

算法的优缺点：

不同的算法，性能高低不同。

算法的作用：

解决问题的技巧。不同的问题，可以选择不同解决方式。

二分查找法：

定义:在一个有序的元素列表中，查找元素是否包含在列表，或者是具体在某个索引位置。

EX:

例如我们要在100个有序的数组中，找到40这个数，那么在数组的哪个位置呢？

笨方法:一个挨着一个的找。找100次就找到了。

好方法：折半查找,首先找出整个数组中的中位数和要查找的数，做比较。

分为两堆，一堆大数，一堆小数。如果中间数<查找数，那么就从大数堆里去找。

再把大数堆分为两堆，以此类推。就最终能到找到，你要找的数。

图片来自《算法图解》

代码如下：

说到算法，接下来就得说下“大O表示法”。

大O表示法 是一种特殊的表示法，指出了算法的速度有多快。

之前提到笨方法，就是线性时间 O(n) , n:表示操作数。

二分查找法，就是对数时间 O(logn)。查找100个数的数组，最多只要7次。

(log^100,log指的是log2,log2^100相当于问“将多少个2相乘的结果为100”)

如果忘了对数是什么？请自行百度一下。由于不是这次主要内容，这里就不展开介绍。

今天，就给大家分享到这。明天会继续分享《选择排序+数组和链表》。

PS:

如果你阅读之后，有所收获。请记得点赞哦。o(*￣︶￣*)o。你的支持将是我写作的动力。