深度优先搜索和广度优先搜索

深度优先

DFS Depth First Search

遍历方式
1. 递归
2. 非递归，使用循环遍历，需要栈后进先出的特性来辅助

广度优先

BFS Breadth First Search

遍历方式
1. 循环遍历，需要队列先进先出的特性来辅助

贪心算法 Greedy

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致结果是全局最好或最优的算法。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如:求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。

一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心算法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

贪心算法的应用场景

简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。

二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二分查找的前提

1. 目标函数单调性(单调递增或者递减)
2. 存在上下界(bounded)，溢出问题
3. 能够通过索引访问(index accessible)

二分查找应用场景的局限性

1. 二分查找依赖的是顺序表结构，简单点说就是数组
2. 二分查找针对的是有序数据
3. 数据量太小不适合二分查找
4. 数据量太大也不适合二分查找

二分查找的应用场景

1. 查找第一个值等于给定值的元素
2. 查找最后一个值等于给定值的元素
3. 查找第一个大于等于给定值的元素
4. 查找最后一个小于等于给定值的元素

nick

微信支付

支付宝