遇到问题时，

• 如果不确定该如何 高效地解决，可尝试 分而治之 或 动态规划；
• 如果认识到 根本就没有高效的解决方案，可转而使用 贪心 来得到 近似答案。

参考书籍：《算法图解》

查找

二分查找

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

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

这是简单查找，每次猜测都只能排除一个数字。如果我想的数字是 99，你得猜 99 次才能猜到！

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

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

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

这就是 二分查找，每次猜测排除的数字个数如下。

不管我心里想的是哪个数字，你在 7 次之内都能猜到，因为每次猜测都将排除很多数字！

代码

函数 binary_search 接受一个 有序数组 和 一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。

完整的代码如下：

def binary_search(nums, item):
    low = 0  # low 和 high 用于跟踪要在其中查找的列表部分
    high = len(nums) - 1  # 查找范围的高部分

    while low <= high:
        mid = (low + high)  # 只要范围没有缩小到只包含一个元素，就检查中间的元素
        guess = nums[mid]
        if guess == item:  # 找到了元素
            return mid
        if guess > item:  # 猜的数字太大了
            high = mid - 1
        else:  # 猜的数字太小了
            low = mid + 1

    return None  # 没有指定的元素

my_list = [1, 3, 5, 7, 9]  # 来测试一下！

print(binary_search(my_list, 3))  # => 1 （别忘了索引从0开始，第二个位置的索引为1）
print(binary_search(my_list, -1))  # => None （在 Python 中，None 表示空，它意味着没有找到指定的元素）

查找算法的运行时间：

大 O 表示法

大O时间复杂度的常见情况（按快到慢排序）：

• O(log n)：对数时间，如二分查找。
• O(n)：线性时间，如简单查找。
• O(n log n)：如快速排序（效率较高的排序算法）。
• O(n²)：如选择排序（效率较低的排序算法）。
• O(n!)：如旅行商问题的暴力解法（极其低效的算法）。

假设你要绘制一个包含 16 格的网格，且有 5 种不同的算法可供选择，这些算法的运行时间如上所示。如果你选择第一种算法，绘制该网格所需的操作数将为 4（log 16 = 4）。假设你每秒可执行 10 次操作，那么绘制该网格需要 0.4 秒。如果要绘制一个包含 1024 格的网格呢？这需要执行 10 （log 1024 = 10）次操作，换言之，绘制这样的网格需要 1 秒。这是使用第一种算法的情况。

第二种算法更慢，其运行时间为 O(n)。即要绘制 16 个格子，需要执行 16 次操作；要绘制 1024 个格子，需要执行 1024 次操作。执行这些操作需要多少秒呢？

总结，

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

广度优先搜索

广度优先搜索是一种 用于图的查找算法，可帮助回答两类问题。

• 第一类问题：从节点 A 出发，有前往节点 B 的路径吗？
• 第二类问题：从节点 A 出发，前往节点 B 的哪条路径最短？

假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。在 Wechat，你与芒果销售商有联系吗？为此，你可在朋友中查找。

这种查找很简单。首先，创建一个朋友名单。

然后，依次检查名单中的每个人，看看他是否是芒果销售商。

假设你没有朋友是芒果销售商，那么你就必须在朋友的朋友中查找。

检查名单中的每个人时，你都将其朋友加入名单。

这样一来，你不仅在朋友中查找，还在朋友的朋友中查找。别忘了，你的目标是在你的人际关系网中找到一位芒果销售商。因此，如果 Alice 不是芒果销售商，就将其朋友也加入到名单中。这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个 人际关系网，直到找到芒果销售商。这就是 广度优先搜索算法。

再说一次，广度优先搜索可回答两类问题。

• 第一类问题：从节点 A 出发，有前往节点 B 的路径吗？（在你的人际关系网中，有芒果销售商吗？）
• 第二类问题：从节点 A 出发，前往节点 B 的哪条路径最短？（哪个芒果销售商与你的关系最近？）

刚才你看到了如何回答第一类问题，下面来尝试回答第二类问题——谁是关系最近的芒果销
售商。例如，朋友是一度关系，朋友的朋友是二度关系。

在你看来，一度关系胜过二度关系，二度关系胜过三度关系，以此类推。因此，你应先在一度关系中搜索，确定其中没有芒果销售商后，才在二度关系中搜索。广度优先搜索就是这样做的！

在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。顺便问一句：将先检查 Claire 还是 Anuj 呢？Claire 是一度关系，而 Anuj 是二度关系，因此将先检查 Claire，后检查 Anuj。

也可以这样看，一度关系在二度关系之前加入查找名单。你 按顺序依次检查名单中的每个人，看看他是否是芒果销售商。这将先在一度关系中查找，再在二度关系中查找，因此找到的是关系最近的芒果销售商。广度优先搜索不仅查找从 A 到 B 的路径，而且找到的是最短的路径。

代码

首先，需要使用代码来实现 图。图由多个节点组成。每个节点都与邻近节点相连，如果表示类似于“你→Bob”这样的关系呢？好在你知道的一种结构让你能够表示这种关系，它就是 散列表！

记住，散列表让你能够 将键映射到值。在这里，你要 将节点映射到其所有邻居。

graph = {}
graph["you"] = ["alice", "bob", "claire"]

注意，“你”被映射到了一个数组，因此 graph["you"] 是一个数组，其中包含了“你”的所有邻居。

图不过是一系列的节点和边，因此在 Python 中，只需使用上述代码就可表示一个图。那像下
面这样更大的图呢？

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

顺便问一句：键—值对的添加顺序重要吗？换言之，如果你这样编写代码：

graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []

而不是这样编写代码：

graph["anuj"] = []
graph["claire"] = ["thom", "jonny"]

对结果有影响吗？

在 Python 中，字典（dict）是无序的数据结构（在 Python 3.6 之前）。从 Python 3.7 开始，字典的插入顺序才变得有序，但这通常不会影响使用方式，除非你依赖顺序进行某些操作。

在代码示例中，graph 是一个字典，无论是先添加 "claire" 还是 "anuj"，最终的 graph 结构都是相同的。

Anuj、Peggy、Thom 和 Jonny 都没有邻居，这是因为虽然有指向他们的箭头，但没有从他们
出发指向其他人的箭头。这被称为 有向图（directed graph），其中的关系是单向的。因此，Anuj 是 Bob 的邻居，但 Bob 不是 Anuj 的邻居。无向图（undirected graph）没有箭头，直接相连的节点互为邻居。例如，下面两个图是等价的。

先概述一下这种算法的工作原理。

首先，创建一个队列。在 Python 中，可使用函数 deque 来创建一个双端队列。

from collections import deque
search_queue = deque()  # 创建一个队列
search_queue += graph["you"]  # 将你的邻居加入到这个队列

graph["you"] 是一个数组，其中包含你的所有邻居，如 ["alice", "bob","claire"]。这些邻居都将加入到搜索队列中。

while search_queue:    # 只要队列不为空
   	person = search_queue.popleft()   # 就取出其中的第一个人
   	if person_is_seller(person):  # 检查这个人是否是芒果销售商
   	    print person + " is a mango seller!"  # 是芒果销售商
   	    return True
  	else:
    	search_queue += graph[person]   # 不是芒果销售商。将这个人的朋友都加入搜索队列

return False    # 如果到达了这里，就说明队列中没人是芒果销售商

下面来看看广度优先搜索的执行过程。

这个算法将不断执行，直到满足以下条件之一：

• 找到一位芒果销售商；
• 队列变成空的，这意味着你的人际关系网中没有芒果销售商。

Peggy 既是 Alice 的朋友又是 Bob 的朋友，因此她将被加入队列两次：一次是在添加 Alice 的朋友时，另一次是在添加 Bob 的朋友时。因此，搜索队列将包含两个 Peggy。

但你只需检查 Peggy 一次，看她是不是芒果销售商。如果你检查两次，就做了无用功。因此，检查完一个人后，应将其标记为已检查，且不再检查他。如果不这样做，就可能会导致无限循环。假设你的人际关系网类似于下面这样。

搜索队列将在包含你和包含 Peggy 之间反复切换。

检查一个人之前，要确认之前没检查过他，这很重要。为此，你可使用一个
列表来记录检查过的人。

考虑到这一点后，广度优先搜索的最终代码如下。

def search(name):
	search_queue = deque()
	search_queue += graph[name]
	searched = []        # 这个数组用于记录检查过的人
	while search_queue:
		person = search_queue.popleft()
		if not person in searched:      # 仅当这个人没检查过时才检查
			if person_is_seller(person):
				print person + " is a mango seller!"
				return True
			else:
				search_queue += graph[person]
				searched.append(person)        # 将这个人标记为检查过
	return False

search("you")

如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是从一个人到另一个人的箭头或连接），因此运行时间至少为 O(边数)。

你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为 O(1)，因此对每个人都这样做需要的总时间为 O(人数)。所以，广度优先搜索的运行时间为 O(人数 + 边数)，这通常写作 O(V + E)，其中 V 为顶点（vertice）数，E 为边数。

狄克斯特拉算法

递归

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。

递归 指的是 自己调用自己的函数。

编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线
条件（base case）和递归条件（recursive case）。

• 递归条件 指的是函数调用自己，
• 而 基线条件 则指的是函数不再调用自己，从而避免形成无限循环。

递归调用栈

递归函数也使用调用栈！来看看递归函数 factorial 的调用栈。factorial(5) 写作 5!，其定义如下：5! = 5 * 4 * 3 * 2 * 1。同理，factorial(3) 为 3 * 2 * 1。下面是计算阶乘的递归函数。

def fact(x):
  if x == 1:
    return 1
  else:
    return x * fact(x-1)

下面来详细分析调用 fact(3) 时调用栈是如何变化的。栈顶的方框指出了当前执行到了什么地方。

注意，每个 fact 调用都有自己的 x 变量。在一个函数调用中不能访问另一个的 x 变量。

分而治之（divide and conquer，D&C）

分治 是一种著名的 递归式问题解决方法。其工作原理是：

• 找出简单的 基线条件；
• 确定 如何缩小问题的规模，使其符合基线条件。

给定一个数字数组 [2, 4, 6]，你需要将这些数字相加，并返回结果。使用循环很容易完成这种任务，但如何使用递归函数来完成这种任务呢？

第一步：找出基线条件。最简单的数组什么样呢？如果数组不包含任何元素或只包含一个元素，计算总和将非常容易。

第二步：每次递归调用都必须离空数组更近一步。如何缩小问题的规模呢？下面是一种办法。

这与下面的版本等效。

这两个版本的结果都为 12，但在第二个版本中，给函数 sum 传递的数组更短。换言之，这缩
小了问题的规模！这个函数的运行过程如下。

编写涉及数组的递归函数时，基线条件 通常是 数组为空 或 只包含一个元素。陷入困境时，请检查基线条件是不是这样的。

贪心

教室调度问题

假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。

你没法让这些课都在这间教室上，因为有些课的上课时间有冲突。

你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢？

这个问题好像很难，不是吗？实际上，算法可能简单得让你大吃一惊。具体做法如下。

• 选出结束最早的课，它就是要在这间教室上的第一堂课。
• 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。

重复这样做就能找出答案！下面来试一试。美术课的结束时间最早，为 10:00 a.m.，因此它
就是第一堂课。

接下来的课必须在 10:00 a.m. 后开始，且结束得最早。英语课不行，因为它的时间与美术课冲突，但数学课满足条件。最后，计算机课与数学课的时间是冲突的，但音乐课可以。

因此将在这间教室上如下三堂课。

贪心算法很简单：每步都采取最优的做法。在这个示例中，你每次都选择结束最早的课。用专业术语说，就是 你每步都选择局部最优解，最终得到的就是全局最优解。

贪婪算法并非在任何情况下都行之有效，但它易于实现！

背包问题

假设你是个贪婪的小偷，背着可装 35 磅（1磅≈0.45千克）重东西的背包，在商场伺机盗窃各种可装入背包的商品。

你力图往背包中装入价值最高的商品，你会使用哪种算法呢？同样，你采取贪婪策略，这非常简单。

• 盗窃可装入背包的最贵商品。
• 再盗窃还可装入背包的最贵商品，以此类推。

只是这次这种贪婪策略不好使了！例如，你可盗窃的商品有下面三种。

你的背包可装 35 磅的东西。音响最贵，你把它给偷了，但背包没有空间装其他东西了。

你偷到了价值 3000 美元的东西。且慢！如果不是偷音响，而是偷笔记本电脑和吉他，总价将
为 3500 美元！

在这里，贪婪策略显然不能获得最优解，但非常接近。

集合覆盖问题

假设你办了个广播节目，要让全美 50 个州的听众都收听得到。为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。

动态规划

背包问题

假设你是个小偷，背着一个可装 4 磅东西的背包。你可盗窃的商品有如下 3 件。

为了让盗窃的商品价值最高，你该选择哪些商品？

动态规划先解决子问题，再逐步解决大问题。

对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。

每个动态规划算法都从一个网格开始，背包问题的网格如下。

网格的各行为商品，各列为不同容量（1～4磅）的背包。所有这些列你都需要，因为它们将帮助你计算子背包的价值。

网格最初是空的。你将填充其中的每个单元格，网格填满后，就找到了问题的答案！你一定要跟着做。请你创建网格，我们一起来填满它。

首先来看第一行。这是吉他行，意味着你将尝试将吉他装入背包。在每个单元格，都需要做一个简单的决定：偷不偷吉他？别忘了，你要找出一个价值最高的商品集合。

第一个单元格表示背包的容量为 1 磅。吉他的重量也是 1 磅，这意味着它能装入背包！因此这个单元格包含吉他，价值为 1500 美元。

与这个单元格一样，每个单元格都将包含当前可装入背包的所有商品。来看下一个单元格。这个单元格表示背包的容量为 2 磅，完全能够装下吉他！

这行的其他单元格也一样。别忘了，这是第一行，只有吉他可供你选择。换言之，你假装现在还没法盗窃其他两件商品。

此时你很可能心存疑惑：原来的问题说的是 4 磅的背包，我们为何要考虑容量为 1 磅、2 磅等的背包呢？前面说过，动态规划从小问题着手，逐步解决大问题。这里解决的子问题将帮助你解决大问题。

我们来填充下一行——音响行。你现在出于第二行，可偷的商品有吉他和音响。在每一行，可偷的商品都为当前行的商品以及之前各行的商品。因此，当前你还不能偷笔记本电脑，而只能偷音响和吉他。我们先来看第一个单元格，它表示容量为 1 磅的背包。在此之前，可装入 1 磅背包的商品的最大价值为 1500 美元。

背包的容量为 1 磅，能装下音响吗？音响太重了，装不下！由于容量 1 磅的背包装不下音响，因此最大价值依然是 1500 美元。

接下来的两个单元格的情况与此相同。在这些单元格中，背包的容量分别为 2 磅和 3 磅，而以前的最大价值为 1500 美元。

由于这些背包装不下音响，因此最大价值保持不变。背包容量为 4 磅呢？终于能够装下音响了！原来的最大价值为 1500 美元，但如果在背包中装入音响而不是吉他，价值将为 3000 美元！因此还是偷音响吧。

你更新了最大价值！如果背包的容量为 4 磅，就能装入价值至少 3000 美元的商品。在这个网格中，你逐步地更新最大价值。

下面以同样的方式处理笔记本电脑。笔记本电脑重 3 磅，没法将其装入容量为 1 磅或 2 磅的背包，因此前两个单元格的最大价值还是 1500 美元。

对于容量为 3 磅的背包，原来的最大价值为 1500 美元，但现在你可选择盗窃价值 2000 美元的笔记本电脑而不是吉他，这样新的最大价值将为 2000 美元！

对于容量为 4 磅的背包，情况很有趣。这是非常重要的部分。当前的最大价值为 3000 美元，你可不偷音响，而偷笔记本电脑，但它只值 2000 美元。

价值没有原来高。但等一等，笔记本电脑的重量只有 3 磅，背包还有 1 磅的容量没用！

在 1 磅的容量中，可装入的商品的最大价值是多少呢？你之前计算过。

根据之前计算的最大价值可知，在 1 磅的容量中可装入吉他，价值 1500 美元。因此，你需要做如下比较。

你可能始终心存疑惑：为何计算小背包可装入的商品的最大价值呢？但愿你现在明白了其中的原因！余下了空间时，你可根据这些子问题的答案来确定余下的空间可装入哪些商品。笔记本电脑和吉他的总价值为 3500 美元，因此偷它们是更好的选择。

最终的网格类似于下面这样。

答案如下：将吉他和笔记本电脑装入背包时价值最高，为 3500 美元。

计算每个单元格的价值时，使用的公式都相同。

你可以使用这个公式来计算每个单元格的价值，最终的网格将与前一个网格相同。现在你明白了为何要求解子问题吧？你可以合并两个子问题的解来得到更大问题的解。

旅游行程最优化

假设你要去伦敦度假，假期两天，但你想去游览的地方很多。你没法前往每个地方游览，因此你列个单子。

对于想去游览的每个名胜，都列出所需的时间以及你有多想去看看。根据这个清单，你能确定该去游览哪些名胜吗？

这也是一个背包问题！但约束条件不是背包的容量，而是有限的时间；不是决定该装入哪些商品，而是决定该去游览哪些名胜。请根据这个清单绘制动态规划网格，再接着往下读。

网格类似于下面这样。

你画对了吗？请填充这个网格，决定该游览哪些名胜。答案如下。