二分查找与大O表示法

夏天就要过去了，有点舍不得……

二分查找

先思考一个简单的问题，1-100的数字，让你猜出我想好的其中一个数，你每猜一次我会说大了或者小了或者对了。你的猜测过程会是怎样的呢？

假如依次往上猜，这种方法叫做简单查找，如果我想好的数字是100那么你将猜100次。

那么比这个更好的方法就是二分查找法：从50开始猜，一次就排除了一半，依此类推，我说小了，下次就从猜75……，你猜到100只需要7次，和简单查找相比是不是快了很多。

一般而言，对于包含n个元素的列表，用二分查找最多需要log2(n)步，简单查找最多n步。注意，当列表是有序的时候，二分查找法才管用哦！

大O表示法

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

上面例子中简单查找法用大O表示法表示运行时间是：O(n)。二分查找法用大O表示法表示的运行时间是：O(log n)。

大O表示法指出了最糟情况下的运行时间。

常见的大O运行时间：

• O(log n) ,对数时间，二分查找法
• O(n),线性时间，简单查找
• O(n*log n)，快速排序
• O(n²)，选择排序
• O(n!)，阶乘时间

Tips:

• 算法的速度所指并非时间，而是操作数的增速
• 算法的运行时间用大O表示法表示
• O(log n)与O(n)相比，当需要搜索的元素越多，前者比后者快的越多

愿我们有能力不向生活缴械投降---Lin