算法图解
1.2 二分查找
二分查找是一种算法，其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要 查找的元素包含在列表中，二分查找返回其位置;否则返回null。
一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。
可将一系列元素存储在一系列相邻的桶(bucket)，即数组中。这些桶从0开始编号:第一个桶的位置为#0，第二个桶为#1，第三个桶为#2，以此类推。
1.3 大O表示法是一种特殊的表示法，指出了算法的速度有多快。
大O表示法指的并非以秒为单位的速度。大O表示法 让你能够比较操作数，它指出了算法运行时间的增速。
1.3.4 一些常见的大O运行时间 下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
O(log n)，也叫对数时间，这样的算法包括二分查找。
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
我们获得的主要启示如下。
算法的速度指的并非时间，而是操作数的增速。
谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
算法的运行时间用大O表示法表示。
O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
1.4 小结
二分查找的速度比简单查找快得多。
O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。 算法运行时间并不以秒为单位。
算法运行时间是从其增速的角度度量的。
算法运行时间用大O表示法表示。
需要同时读取所有元素时，链表的效率很高:读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率 真的很低。
需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。
在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存地址，必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素 的地址，以此类推，直到访问第五个元素。
元素的位置称为索引。因此，不说“元素20的位置为1”，而说“元素20位于索引1处”。本书 将使用索引来表示位置。
需要在中间插入元素时，数组和链表哪个更好呢?使用链表时，插入元素很简单，只需修改 它前面的那个元素指向的地址。
而使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，可能还得将整个数组复制到其他地方!因此，当需要在中间插入元素时，链表是更好的选择。
如果你要删除元素呢?链表也是更好的选择，因为只需修改前一个元素指向的地址即可。而使用数组时，删除元素后，必须将后面的元素都向前移。
不同于插入，删除元素总能成功。如果内存中没有足够的空间，插入操作可能失败，但在任何情况下都能够将元素删除。
需要指出的是，仅当能够立即访问要删除的元素时，删除操作的运行时间才为O(1)。通常我 们都记录了链表的第一个元素和最后一个元素，因此删除这些元素时运行时间为O(1)。
有两 种访问方式:随机访问和顺序访问。
顺序访问意味着从第一个元素开始逐个地读取元素。
链表只能顺序访问:要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随机 10 访问意味着可直接跳到第十个元素。
本书经常说数组的读取速度更快，这是因为它们支持随机访问。
很多情况都要求能够随机访问，因此数组用得很多。
总结：数组查找快，增删改慢。链表查找慢，增删改快。
练习
1.1 假设你要为饭店创建一个接受顾客点菜单的应用程序。这个应用程序存储一系列点菜 单。服务员添加点菜单，而厨师取出点菜单并制作菜肴。这是一个点菜单队列:服务 员在队尾添加点菜单，厨师取出队列开头的点菜单并制作菜肴。
你使用数组还是链表来实现这个队列呢?(提示:链表擅长插入和删除，而数组擅长 随机访问。在这个应用程序中，你要执行的是哪些操作呢?)
数组，只需要查找。
1.2 我们来做一个思考实验。假设Facebook记录一系列用户名，每当有用户试图登录 Facebook时，都查找其用户名，如果找到就允许用户登录。由于经常有用户登录 Facebook，因此需要执行大量的用户名查找操作。假设Facebook使用二分查找算法， 而这种算法要求能够随机访问——立即获取中间的用户名。考虑到这一点，应使用数 组还是链表来存储用户名呢?
数组，查找快
1.3 经常有用户在Facebook注册。假设你已决定使用数组来存储用户名，在插入方面数组 有何缺点呢?具体地说，在数组中添加新用户将出现什么情况?
数组默认内存占用可能不足以插入新用户，最终创建新数组来插入新用户。
1.4 实际上，Facebook存储用户信息时使用的既不是数组也不是链表。假设Facebook使用 的是一种混合数据:链表数组。这个数组包含26个元素，每个元素都指向一个链表。
例如，该数组的第一个元素指向的链表包含所有以A打头的用户名，第二个元素指向的 链表包含所有以B打头的用户名，以此类推。
假设Adit B在Facebook注册，而你需要将其加入前述数据结构中。因此，你访问数组的 第一个元素，再访问该元素指向的链表，并将Adit B添加到这个链表末尾。现在假设你要查找Zakhir H。因此你访问第26个元素，再在它指向的链表(该链表包含所有以z打头的用户名)中查找Zakhir H。
请问，相比于数组和链表，这种混合数据结构的查找和插入速度更慢还是更快?你不必给出大O运行时间，只需指出这种新数据结构的查找和插入速度更快还是更慢。
是，快
2.3 选择排序
需要检查的元素数越来越少
随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一 个。既然如此，运行时间怎么还是O(n2)呢?这个问题问得好，这与大O表示法中的常数相关。 第4章将详细解释，这里只简单地说一说。
你说得没错，并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素 数依次为n 1, n – 2, …, 2和1。平均每次检查的元素数为1/2 × n，因此运行时间为O(n × 1/2 × n)。 但大O表示法省略诸如1/2这样的常数(有关这方面的完整讨论，请参阅第4章)，因此简单地写 作O(n × n)或O(n2)。
选择排序是一种灵巧的算法，但其速度不是很快。快速排序是一种更快的排序算法，其运行 时间为O(n log n)
2.4 小结
计算机内存犹如一大堆抽屉。
需要存储多个元素时，可使用数组或链表。
数组的元素都在一起。
链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
数组的读取速度很快。
链表的插入和删除速度很快。
在同一个数组中，所有元素的类型都必须相同(都为int、double等)。
3.1 递归
递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。
编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。