AndroidX技术栈之经典算法
一、二分查找法
//二分查找
int binarySearch(int arr[], int len, int key)
{
int left = 0;
int right = len - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (key < arr[mid]) {//key在左边
right = mid - 1;
} else if (arr[mid] < key) {//key在右边
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
二、递归
递归算法：直接或者间接不断反复调用自身来达到解决问题的方法。要求原始问题可以分解为相同问题的子问题。
算法操作：1 递归边界 2 自身调用
特点分析：递归思路简单清晰，如果分析出将很快得到结果;递归将多次调用，使用到堆栈，算法效率低，费时费内存。
常用场景：阶乘，斐波纳契数列、汉诺塔问题，整数划分，枚举排列及二叉树，图的搜索相关问题。
算法参考：https://blog.csdn.net/yanerhao/article/details/64438251
三、回溯算法
回溯算法在解决多选择问题时特别有效，一般思路如下：在当前场景下，存在若干种选择去操作，有可能两种结果：一是违反相应条件限制，只能返回（back），另一种是该选择选到最后居然正确并结束。故在回溯时存在三要素，能总结出这样的三要素问题便可以迅速解决：1 找到选择。2 限制条件，即选择操作在此条件下才进行。3 结束
使用场景：回溯算法是深度优先策略的典型应用，回溯算法就是沿着一条路向下走，如果此路不同了，则回溯到上一个分岔路，在选一条路走，一直这样递归下去，直到遍历万所有的路径。八皇后问题是回溯算法的一个经典问题，还有一个经典的应用场景就是迷宫问题。
算法参考：https://blog.csdn.net/yanerhao/article/details/68561290
四、动态规划
动态规划：首先需要决定存储什么历史信息，以及用什么数据结构来存储。然后最重要的就是递推公式，最后需要考虑起始条件的值。动态规划法从后往前，引出递推公式。
算法参考：https://blog.csdn.net/yanerhao/article/details/69944971
五、贪心算法
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，贪心策略使用的前提是局部最优能导致全局最优。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
贪心算法的基本思路：
（1）建立数学模型来描述问题。
（2）把求解的问题分成若干个子问题。
（3）对每一子问题求解，得到子问题的局部最优解。
（4）把子问题的解局部最优解合成原来解问题的一个解。
实现算法框架：
从问题的某一初始解出发；
while （能朝给定总目标前进一步）{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
算法参考：https://blog.csdn.net/yanerhao/article/details/70162902
六、分治法
分治法又名分而治之算法，分治算法就是把一个大的问题分为若干个子问题，然后在子问题继续向下分，一直到base cases，通过base cases的解决，一步步向上，最终解决最初的大问题。分治算法是递归的典型应用。
算法参考：http://blog.csdn.net/changyuanchn/article/details/17150109
七、分支限界算法
回溯算法是深度优先，那么分支限界法就是广度优先的一个经典的例子。回溯法一般来说是遍历整个解空间，获取问题的所有解，而分支限界法则是获取一个解（一般来说要获取最优解）。
算法参考：http://blog.csdn.net/changyuanchn/article/details/17102037
经典算法讲解：