《图解算法》作者是 Aditya Y. Bhargava，内容浅显易懂，他的个人博客 adit.io 干货内容不少，有丰富插图，十分有趣。本书在亚马逊有 kindle 版。
本书代码使用 Python 2.7。
以下是读书笔记的内容。
1.2 二分查找
比如：登录 Facebook，核实账户是否存在。
对于包含 n 个元素的列表，用二分查找最多需要 \(log_2{n}\) 步。
仅当列表是有序时，二分查找才管用。
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) / 2
guess = list[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
print binary_search(my_list, -1) # => None
运行时间
简单查找最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。
二分查找的运行时间为对数时间（或 \(log\) 时间）。
1.3 大 \(O\) 表示法
大 \(O\) 表示法指出算法有多快。比如，简单查找的运行时间为 \(O(n)\)，二分查找法的运行时间是 \(O(log_2{n})\)。
1.3.4 一些常见的大 \(O\) 运行时间
- \(O(log_2{n})\) 也称对数时间，此类算法包括二分查找。
- \(O(n)\) 也称线性时间，此类算法包括简单查找。
- \(O(n * log_2{n})\) 此类算法包括快速排序，一种速度较快的排序算法。
- \(O(n^2)\) 此类算法包括选择排序，一种速度较慢的排序算法。
- \(O(n!)\) 也称阶乘时间，此类算法包括旅行商问题的解决方案，一种非常慢的算法。
2.1 内存的工作原理
计算机就像是很多抽屉的集合体，每个抽屉都有地址。
2.2 数组和链表
数组添加新元素的速度会很慢。而且必须是排列在一起。数组随机读取效率很高。
链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。犹如寻宝游戏。
链表无需移动元素。链表随机读的效率很低，需要从第一个元素开始读取。
常见的数组和链表操作的运行时间如下：
| 数组 | 链表 | |
|---|---|---|
| 读取 | \(O(1)\) | \(O(n)\) |
| 插入 | \(O(n)\) | \(O(1)\) |
| 删除 | \(O(n)\) | \(O(1)\) |
当需要在中间插入元素或删除元素时，链表是更好的选择。
当需要随机访问时，推荐使用数组。