二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回 null，使用二分查找时，每次猜测的是中间的数字，从而将余下的数字排除一半。（仅仅当列表是有序的时候，二分查找才管用）
一般而言，对于包含n个元素的列表查找某个元素，使用二分法最多需要 \(log_{2}n\) 步(**时间复杂度为 \(log_{2}n\) **)，简单查找最多需要 n 步。大 O 表示法指出了算法最糟糕情况下的运行时间。二分法实例代码如下：
有序数组中的目标出现多次，利用二分查找返回在最左边出现的目标值或者是最右边出现的目标值，实例代码如下：
在计算机中，存储多项数据时，有两种基本方式－数组和链表。但它们并非适用于所有情形。
链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。链表结构直观显示如下图所示：
链表的优势在插入元素方面，那数组的优势又是什么呢？
需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存 地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素 的地址，以此类推，直到访问第五个元素。
数组的元素带编号，编号从 0 而不是 １ 开始，几乎所有的编程语言都从０开始对数组元素进行编号，比如C/C++的数组结构和Python的列表结构。元素的位置称为索引。下面是常见数组和链表操作的运行时间.
学习如何将问题分成基线条件和递归条件，学习如何使用递归算法，递归算法直观上更好理解，步骤简单。
编写递归函数时，必须告诉它何时停止，因此，每个递归函数有两个部分：基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己，而基线条件则 指的是函数不再调用自己，从而避免形成无限循环。
栈的定义：栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。调用栈(call stack)
计算机在内部使用被称为调用栈的栈。调用另一个函数时，当前函数暂停 并处于未完成状态。该函数的所有变量的值都还在内存中。栈顶的方框指出了当前执行 到了什么地方。
栈在递归中扮演着重要角色。使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况 下，你有两种选择。
快速排序使用分而治之的策略，分而治之是我们学习的第一种通用的问题解决办法。分而治之(divide and conquer，D&C)-一种著名的递归式问题解决办法。
D&C算法是递归的。使用D&C解决问题的过程包括两个步骤：
D&C并非可直接用于解决问题的算法，而是一种解决问题的思路。
C语言标准库中的函数qsort实现的就是快速排序。快速排序也是用了D&C思想。对数组进行快速排序，步骤如下：
上面的代码空间复杂度很大，真正的快排是原地排序，空间复杂度为O(1)，代码如下：
由对数的换底公式，\(log_a n\) 和 \(log_b n\) 只有一个常数因子不同，这个因子在大O记法中被丢弃。因此记作\(O(log n)\)，而不论对数的底是多少，是对数时间算法的标准记法。
数组和链表结构可以用以查找，栈不行。散列表也叫哈希表(Hash table)，散列表有些类似 Python 中的字典 dict 结构。散列表可用以：
给两个键分配的位置相同，这被称为冲突（collision）。处理冲突最简单的办法就是：如果两个键映射到了同一个位置，就在这个位置存储一个链表。
在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速 度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。 因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：
散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。 你可能很快会发现自己经常在使用它。
图算法：广度优先搜索（breadth-first search, BFS）算法广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：
解决最短路径问题的算法被称为广度有限算法，一般步骤为：
图由节点（node）和边（edge）组成。
在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。
图中每个节点都与相邻节点相连，散列表结构可以表示这种关系。图分为有向图（directed graph）和无向图（undirected graph），有向图关系是单向的，无向图没有箭头，直接相连的节点互为邻居。对从自己出发有指向他人的箭头，则有邻居。
如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是从一个人到另一个人的箭头或连接），因此运行时间至少为 \(O(边数)\)。你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为 \(O(1)\)，因此对每个人都这样做需要的总时间为 \(O(人数)\)。所以，广度优先搜索的运行时间为 \(O(人数 + 边数)\)，这通常写作 \(O(V + E)\)，其中 \(V\) 为顶点（ vertice）数， \(E\) 为边数。
迪克斯特拉算法能够找出加权图中前往X的最短路径。对于寻找耗时最少的路径，迪克斯特拉算法包含４个步骤：
图可能有环，所谓环，是指由一个节点出发，走一圈后可以又回到原节点，如下图所示：
因此， 不能将狄克斯特拉算法用于包含负权边的图。在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼福德算法（ Bellman-Ford algorithm）。
以下图为例，编程实现耗时最短的路径。
代码如下：
贪婪算法思想很简单：每步都采取最优的做法，专业术语说，就是每步都选择局部最优解，最终得到的就是全局最优解。
根据给定课表，尽可能将更多的课程安排在某间教室。解决办法：贪婪算法可找到最优解。
背包重量有限，根据策略使得装入背包的物品价值最高。在这里， 贪婪策略显然不能获得最优解，但非常接近。在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。
代码实例：
程序输出如下：
贪心算法的实质是每次选出当前的最优解，不管整体，是基于一定假设下的最优解。
旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。
NP 完全问题无处不在！如果能够判断出要解决的问题属于 NP 完全问题就好了，这样就不用 去寻找完美的解决方案，而是使用近似算法即可。但要判断问题是不是NP完全问题很难，易于解决的问题和 NP 完全问题的差别通常很小。
但如果要找出经由指定几个点的的最短路径，就是旅行商问题——NP完全问题。简言之，没办法判断问题是不是 NP 完全问题，但还是有一些蛛丝马迹可循的。
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。在学习动态规划之前需要明确掌握几个重要概念，如下：
学习动态规划，这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题，每个动态规划问题都是从一个网格入手，背包问题的网格如下：
工作原理：动态规划先解决子问题，再逐步解决大问题。从背包问题的网格计算入手，可明白为何计算小背包可装入的商品的最大价值。余下了空间时，你可根据这些子问题的答案来确定余下的空间可装入哪些商品。计算每个单元格的价值时，使用的公式都相同。 这个公式如下：
网格的行顺序发生变化时，最终答案没有变化。各行的排列顺序对最终结果无关紧要。
动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。 但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。 这意味着使用动态规划算 法解决不了去巴黎玩的问题。