vlambda博客
学习文章列表

title: 算法介绍1-二分查找、大O表示法 

date: 2019-12-27 13:12:36 

tags: 技术

前言

本人对算法有些兴趣，正好最近不知道写什么，所以就想介绍一些算法，内容大部分取自《算法图解》——一本很生动的算法介绍书。书里面的代码是用python所写，但因为现在大家学的几乎都是C语言，所以代码部分我将用C语言重现一遍，如果对文章内容和代码有疑问的欢迎评论或者私信我哦。

二分查找

又假设要在字典中找一个以O开头的单词，你也将从中间附近开始。

这是一个查找问题，在上述情况下，都可以使用同一种算法来解决问题，这种算法就是二分查找。

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置，否则返回NULL。

下面的示例说明了二分查找的工作原理。我随便想一个1～100的数字。

你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。

假设你从1开始往上猜，猜测过程会是这样：

你：“1”， 我：“小了”

你：“2”， 我：“小了“

.

.

.

你：“7”， 我：“小了”， 你：“我佛辣...”

更佳的查找方式

下面是一种更好的猜法。从50开始。

你：“50”， 我：“小了”

小了，但排除了一半的数字！至此，你知道1～50都小了。接下来，你猜75。

你：“75”， 我：“大了”

大了！那剩余的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜63 (50和75中间的数字)。

你：“63”， 我：“大了”

你：“57”， 我：“对了！”

这就是二分查找！恭喜你学会了第一种算法！每次猜测排除的数字个数如下。

在1～100中，不管我心里想的是哪个数字，你在7次之内都可以猜到，因为每次猜测都可以排除很多数字！

假设你要在字典中查找一个单词，而该字典包含240 000个单词，你认为每种查找最多需要多少步？

• 如果要查找的单词位于字典末尾，使用简单查找将需要240 000步。
• 使用二分查找时，每次排除一半单词，直到最后只剩下一个单词。

每次排除一半，那就相当于除以2，如此往复除以2，显然我们使用二分查找的步数，就是log₂n步，而简单查找最多需要 n 步。

说明：仅当列表是有序的时候，二分查找才有用处。例如，字典中的单词是按字母顺序排列的，因此可以使用二分查找来查找单词。如果不是按顺序排列的，结果将如何呢？

下面来看看如何编写执行二分查找的C语言代码。这里的代码示例使用了数组。如果你不熟悉数组也不用担心，下次的推文就会介绍。你只需要知道，可将一系列元素存储在一系列相邻的桶(bucket)，即数组中。这些桶从0开始编号:第一个桶的位置为#0，第二个桶为#1，第三个桶为#2，以此类推。

函数binary_search接收一个有序数组和一个元素。如果指定的元素包含在数组中，这个函数返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组。

low = 0;
high = sizeof(arr) - 1; //arr为要查找的数组

你每次都检查中间的元素

mid = (low + (high - low)) / 2;
guess = arr[mid];

如果猜的数字guess小了，就相应修改high

if (guess < arr[mid]) //猜的数字小于中间的数，这时修改high为中间的位置
{
  high = mid - 1; //用mid - 1是因为mid这个位置的数也被排除，所以可以省去
}

如果猜的数字大了，就修改low。完整的代码如下。

int binary_search(int* p, int guess) //传入的p是一个数组
{
 int low = 0, high = sizeof(p) - 1;
 int mid;

 while (low <= high) //只要范围没有缩小到只含有一个元素
 {
 mid = (low + (high - low)) / 2; //就检查中间的元素
 if (p[mid] == guess) //找到了元素
 {
 return mid;
 }
 if (guess < p[mid]) //猜的数字小了
 {
 high = mid - 1;
 }
 else //猜的数字大了
 {
 low = mid + 1;
 }
 }

 return -1; //没有指定元素
}

完整代码如下(可以结合我的动态数组推文食用)

#include <stdio.h>
#include <stdlib.h>

int binary_search(int* p, int guess)
{
 int low = 0, high = sizeof(p) - 1;
 int mid;

 while (low <= high)
 {
 mid = (low + (high - low)) / 2;
 if (p[mid] == guess)
 {
 return mid;
 }
 if (guess < p[mid])
 {
 high = mid - 1;
 }
 else 
 {
 low = mid + 1;
 }
 }

 return -1;
}

int main(void)
{
 int* arr;
 int n;
 int result, guess;

 printf("Please input the size of the array\n");
 scanf("%d", &n);

 arr = (int*)malloc(n * sizeof(int));
 printf("Please input the numbers in order:\n");
 for (int i = 0; i < n; i++)
 {
 scanf("%d", &arr[i]);
 }

 printf("Input the number you want to search:\n");
 scanf("%d", &guess);

 if (binary_search(arr, guess) >= 0)
 {
 printf("Find it ! The position is : %d\n", binary_search(arr, guess));
 }
 else 
 {
 printf("SORRY~I cannot find it !\n");
 }

 free(arr);

 return 0;
}

练习

• 假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请问最多需要几步才能找到？
• 上面列表的长度翻倍后，最多需要几步？

运行时间

每次介绍算法时，我们都将讨论其运行时间。一般而言，应 选择效率最高的算法，以最大限度地减少运行时间或占用空间。

回到前面的二分查找。使用它可以节省多少时间呢？，简单查找逐个检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间(linear time)。

二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表中包含40亿个元素，最多需要猜32次。二分查找的运行时间为对数时间 (或log时间)。

大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快。谁在乎呢?实际上，你经常要 使用别人编写的算法，在这种情况下，知道这些算法的速度大有裨益。

算法的运行时间以不同的速度增加

以上文的二分查找法为例。假设检查一个元素需要1毫秒。使用简单查找时，你必须检查100个元素，因此需要100毫秒才能查找完毕。而使用二分查找时，只需检查7个元素 (log₂100大约为7)，因此需要7毫秒就能查找完毕。然而，实际要查找的列表可能包含10亿个元素，在这种情况下，简单查找需要的时间太多了。

当你使用包含10亿个元素的列表运行二分查找，运行时间为30毫秒 (log₂1 000 000 000大约为30)时。你可能心里想，二分查找的速度大约为简单查找的15倍，因为列表包含100个元素时，简单查找需要100毫秒，二分查找需要7毫秒。因此，列表包含10亿个元素时，简单查找需要30 x 15 = 450毫秒，甚至可以忽略！于是你决定使用简单查找。这是正确的选择吗？

不是！实际上你错的离谱。列表包含10亿个元素时，简单查找需要10亿毫秒， 相当于11天!为什么会这样呢?因为二分查找和简单查找的运行时间的增速不同。随着元素数量的增加，二分查找需要的额外时间并不多， 而简单查找需要的额外时间却很多。因此，随着列表的增长，二分查找的速度比简单查找快得多。有鉴于此，仅知道算法 需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长 而增加。这正是大O表示法的用武之地。

大O表示法指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

举个例子，检查长度为n的列表，二分查找需要执行log₂n次。使用大O表示法，这个运行时间怎么表示？

O(log₂n)

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

简单查找的运行时间总是为O(n)，因为大O表示法说的是最糟的情形。因此，你可以说，这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

一些常见的大O运行时间

下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间

• O(log n)，也叫 对数时间，这样的算法包括二分算法
• O(n)，也叫 线性时间，这样的算法包括简单查找
• O(n * log n)，这样的算法包括 快速排序——一种速度较快的排序算法
• O(n²)，这样的算法包括 选择排序——一种速度较慢的排序算法
• O(n!)，这样的算法包括下一次将介绍的 旅行商问题的解决方案——一种非常慢的算法

还有其他的运行时间，但是这5种是最常见的。

实际上，我们不能如此干净利索地将大O运行时间转换为操作数，但就目前而言，这种准确度足够了。等你学习其他一些算法后，到后面我们将回过头来再次讨论大O表示法。当前，我们获得的主要启示如下。

• 算法的速度指的并非时间，而是操作数的增速。
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
• 算法的运行时间用大O表示法表示。
• O(log n) 比 O(n) 快，当需要搜索的元素越多时，前者比后者快得越多。

练习

使用大O表示法给出下述各种情形的运行时间。

• 在电话簿中根据名字查找电话号码。
• 在电话簿中根据电话号码找人。(提示:你必须查找整个电话簿。)
• 阅读电话簿中每个人的电话号码。
• 阅读电话簿中姓名以A打头的人的电话号码。这个问题比较棘手，它的答案可能让你感到惊讶！