《算法神探》读书笔记
前几天读了《算法神探》，挺有意思一本书，使我对数据结构有了更深理解。笔记如下：
一、二分搜索
1、原理：
请注意，通过这几次的操作，此时虽然下界已经是目标值了（v=15），但是
我们仍需要继续搜索，直到中间值指向目标值。这是因为二分搜索是对中间
值进行判定，而不会判定上界和下界是否是目标值。
如果目标值不在数组中会发生什么呢？在搜索过程中，上下界之间的距
离会越来越近，直到它们之间没有任何还未检查过的值。因为我们总是将其
中一个界限移动到中间值的另一边，所以我们可以在IndexHigh<Indexlow的
时候停下来，这个时候就可以保证目标值不在数组中了。
2、二分搜索法背后的基本思想——
利用数据中的规律去不断地将搜索的范围减半——远比二分搜索法具体的应用更重要。
二、广度优先搜索
1、
广度优先搜索从一个起点开始，慢慢沿着一个边界推进。所以理所当然地它就会由短到长地尝试所有可能的字符串。
如图，搜索算法在尝试完当前层的所有可能密码后，才会进入下一层。
整个广度搜索过程，就像水面上的水波逐步扩散的过程。
2、原理：
广度优先搜索是一个按顺序依次尝试可能的搜索选项的算法。
换句话说，它每次都会选择尝试最先发现的但还没有尝试过的选项。
你可以想象一个列表（更具体地说，是一个队列），上面存着所有已知的
但还没有尝试过的状态（选项）。每一步，算法都会选择从当前队列的第一个状态开始进行尝试。当发现新的可能性时，就将其加到队列的最后，以确保算法在尝试完所有先前已经发现的可能状态后才会去尝试这个新发现的状态。
3、在搜索问题中，如果任意相邻的两个点之间移动的代价（例如所需的时间、体力，等等）是相等的，那么广度优先搜索可以保证找到一条花费最小代价的路径。这是因为它在检查完所有离起点距离X步的点后，才会开始检查那些更远的，例如离起点距离X+1步的点。
三、深度优先搜索
1、我们就是沿着每条路往深处走，直到遇到一条死路。而当遇到死路后，我们就倒退一步，找到我们还没有走过的另一条路走下去。如此反复，直到找到我们的目标为止。
2、深度优先搜索会优先考虑最近新遇到的搜索状态。所以算法会沿着一条路往下走，直到遇到目标状态，或者一条死路（或者一个之前已经探索过的状态）。
和广度优先搜索一样，在使用深度优先搜索时，也可以去维护一个列表（更准确地说，是一个栈），里面存放着所有已知但还未探索过的状态。每一步，算法都会从栈的顶端选出下一步要去探索的状态。
和广度优先搜索一样，我们也会记录下已经探索过的点。这样就可以避免重复探索一个点，这在图里可能有环的时候格外重要。如果不记录的话，你可能会陷入一个环中，无穷无尽地沿着这个环重复探索上面的状态。在上图所示的例子中，我们通过记录下探索过的点来避免将之前已经加入过列表的点（无论它有没有被探索过）再次加入列表。
四、栈与队列
1、在你写深度优先算法的时候，栈有用极了。你只用每次将新的搜索选项放到栈的最顶端，然后在倒退的时候把它们从顶端拿出来就好了。
2、栈和队列是用来存放数据的两种简单的数据结构。表面上看，它们和一个列表没有什么区别，其实它们和列表的区别主要体现在添加和删除数据的方式上。
五、并行算法
1、Frank知道在一个高效的并行算法中很重要的一点便是工作的划分方式，需要保证多个人同时工作所能带来的效率提升高于划分工作所需要的代价。
并行处理会带来一定的额外代价：问题需要被划分成很多部分，每个人需要拿到自己的那一份，并且最后所有人的结果还需要被合并起来。正是因为这些代价，对于一些简单的问题，有时并行处理还不如直接让一个人做。不过，当问题规模变得足够大的时候，并行处理可以很大程度上加速一个算法。
2、想要设计一个高效的并行算法，有两点很重要：
第一是如何高效地将计算任务分割成互相独立的单元；
第二是如何在最后将结果组合起来。
六、迭代加深
1、迭代加深是一个综合深度优先搜索和广度优先搜索的算法。这种算法一轮接一轮地搜索下去，而每一轮都是一个将深度限制为特定长度的深度优先搜索。
2、如果为了跳过那些重复的搜索，直接用深度优先搜索会怎么样？”
“我们会一直沿着一条长的死路走下去，直到我们的咖啡用完。
迭代加深可以让你在那些不幸的情况下不那么惨。它至少限制了你在每一轮中会走多远。
七、逆向索引
1、逆向索引是一个很典型的需要在运行时间和内存占用两者之间取舍的例子。
添加一个逆向索引会占掉更多的内存，但它也让我们在一个新的维度上进行搜索的效率得到了极大提升。
八、二叉搜索树
1、二叉搜索树——一种为了高效查找而设计的数据结构。
2、**递归的意思是将同样的算法作用于一个子问题上。**在我们的问题中，我们将同样的搜索算法作用于子节点上，就是以同样的方法去检查它们。
3、使用二叉搜索树来做区间搜索的优势在于，可以通过剪去大量不可能包含要找的值的分支来减少计算量。
4、和寻找一个值一样，用二叉搜索树做区间搜索只有在需要进行多次搜索时才高效。建立一棵二叉搜索树比搜索一遍数据需要更大的计算量。但是如果要搜索多次，这个计算量可以被均摊到多次搜索里，从而让每次搜索的平均计算量变小。
5、向树中添加节点的过程中，有时会抵消掉平衡二叉搜索树最大的优点之一——算法的高效率。将平衡二叉搜索树的节点数量翻倍时，它的层数只会增加1。这就意味着在搜索一个元素时，即使你将搜索数据的数量翻倍，你的搜索也只需要多进行一步。然而，Socks是对的：这种高效率只有在树左右平衡时才存在。在最坏的情况下，当树成为了一长条直线时，要找一个元素就必须沿着这条直线一直找下去了。而当我们向其中添加任意值的时候，不一定能保证树依然平衡。
6、永远不能让你的客户知道你的成功有多少是建立在别人的愚蠢行为之上的。
九、堆
1、优先队列中的数据并不一定是被排好序的，只能保证按优先级高低顺序提取。
在以后的讲义中你将看到，称为堆的数据结构是一种实现优先队列的有效方式，这种方式并不会完全按顺序保存数据。
2、堆看起来像一棵树，它很容易通过数组来实现。有时为了简单起见，一些堆在实现的时候直接跳过了数组索引0。根节点被放置在索引1处。在这种情况下，索引i处节点的子节点位于索引2×i和2×i+1处，这使得索引计算更为简单。
3、如果你想添加一个元素或删除最大元素，这个过程会更复杂，需要首先打破堆的特性，然后再逐步恢复堆的特性。
为了添加一个新元素，首先将新的元素添加到数组的最后面（即树底层中的第一个空白处）。如果新添加入节点的值大于其父节点的值，这将破坏堆特性，因此需要将此节点向上移动，直到它不再大于其父节点的值，并重新恢复堆的特性。
删除最大值元素也是类似的。将原来的最大值与数组的最后一个元素交换位置，使原来最后的那个元素成为新的根节点。
接下来删除现在最后的这个元素就可以了（此时原来的最大值已经成为数组的最后一个元素）。虽然现在已经正确地删除了原来的最大值的节点，但这个操作也破坏了堆的特性。我们需要从新的根节点开始沿树向下调整该节点，以恢复堆的特性。
此外，由于上述插入和删除操作可以保持树的平衡，所以之后的操作也同样是高效的。
十、the most important
如果你从这门课中只学到了一样东西，那应该是：高效算法的关键在于信息。
当遇到一个新的问题时，应该花些时间理解这个问题的结构和它的数据。
问题拥有的结构越多，你越有可能使用这些信息。
正如你所看到的，在一个有序数组中找到一个值比在一个完全随机的数组中找到一个值要简单得多。有时候，你甚至可以建立附属的数据结构，例如堆或逆向索引，以提供所需要的结构。尽管如此，解决问题的第一步始终应该是理解问题。