此篇写的是非递归算法，递归的在之前的查找算法中写过了。
1.1算法的适用条件
二分查找只适用于从有序的数列中进行查找（比如数字和字母等），将数列排序后在查找。
1.2算法的效率：
实例：使用二分查找的非递归形式对数组{138101167100}进行查找
publicclassBinarySearchNoRecur{publicstaticvoidmain(String[]args){//测试int[]arr={1,3,8,10,11,67,100};intindex=binarySearch(arr,100);System.out.println("index="+index);//}//二分查找的非递归实现/****@paramarr待查找的数组,arr是升序排序*@paramtarget需要查找的数*@return返回对应下标，-1表示没有找到*/publicstaticintbinarySearch(int[]arr,inttarget){intleft=0;intright=arr.length-1;while(left<=right){//说明继续查找intmid=(left+right)/2;if(arr[mid]==target){returnmid;}elseif(arr[mid]>target){right=mid-1;//需要向左边查找}else{left=mid+1;//需要向右边查找}}return-1;}}
2.分治算法
2.1分治算法介绍
1）分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题.....直到最后子问题可以简单的直接求解，原问题的姐即子问题的解的合并。这个技巧是很多高效算法的基础，入排序算法（快排，归并排序），傅里叶变换（快速傅里叶变换）...
2)分治算法可以求解的一些经典问题
2.2分治算法的基本步骤
分治算法在每一层递归上都有三个步骤
1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2）解决：若干问题规模较小而容易被解决则直接解，否则递归地解决各个子问题
3）合并：将各个子问题的解合并为原问题的解。
2.3分治（Divide-andConquer(P)）算法设置模式：
2.4分治算法的实践：汉诺塔（有ABC三个塔）
2.5思路：
1）如果是一个盘，A->C
如果我们有n>=2个盘，我们总是可以看做是两个盘：1.最下面的盘2.上面的盘
（1）先把最上面的盘A->B
(2)把下面的一个盘A->C
(3)把B塔的所有盘从B->C
2.6代码实现：
publicclassHanoitower{publicstaticvoidmain(String[]args){hanoiTower(10,'A','B','C');}//汉诺塔的移动的方法//使用分治算法publicstaticvoidhanoiTower(intnum,chara,charb,charc){//如果只有一个盘if(num==1){System.out.println("第1个盘从"+a+"->"+c);}else{//如果我们有n>=2情况，我们总是可以看做是两个盘1.最下边的一个盘2.上面的所有盘//1.先把最上面的所有盘A->B，移动过程会使用到chanoiTower(num-1,a,c,b);//2.把最下边的盘A->CSystem.out.println("第"+num+"个盘从"+a+"->"+c);//3.把B塔的所有盘从B->C,移动过程使用到a塔hanoiTower(num-1,b,a,c);}}}
3.动态规划算法
应用场景-背包问题
3.1动态规划算法介绍：
1）动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
2）动态规划算法与分治算法类似，其思想也是将待求问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
3）与分治法不同的是，适合于动态规划求解的问题，经分解得到的子问题往往不是相互独立的。（即下一个子阶段的求解是建立在上一个子阶段的解的基础上进行进一步的求解）
4）动态规划可以通过填表的方式来逐步推进，得到最优解。
3.2完全背包与01背包
完全背包指的是：每种物品都有无线件可以使用；01背包只能每件物品取一个。
3.3思路与图解：
3.4代码实现：
4.KMP算法
4.1暴力匹配算法：
4.1.1代码实现
publicclassViolenceMatch{publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstub//测试暴力匹配算法Stringstr1="硅硅谷尚硅谷你尚硅尚硅谷你尚硅谷你尚硅你好";Stringstr2="尚硅谷你尚硅你~";intindex=violenceMatch(str1,str2);System.out.println("index="+index);}//暴力匹配算法实现publicstaticintviolenceMatch(Stringstr1,Stringstr2){char[]s1=str1.toCharArray();char[]s2=str2.toCharArray();ints1Len=s1.length;ints2Len=s2.length;inti=0;//i索引指向s1intj=0;//j索引指向s2while(i 4.2.1KMP算法介绍： 1）KMP算法是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法。 2）Knuth-Morrirs-Pratt字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串P的出现位置，这个算法有DonaldKnuth,VaughanPratt,JamesH.Morris三人于1977年联合发表，故取这三个人名命名此算法。 4.2.2KMP算法的应用 4.2.3思路与图解分析： 举例来说，有一个字符串Str1=“BBCABCDABABCDABCDABDE”，判断，里面是否包含另一个字符串Str2=“ABCDABD”？ 1.首先，用Str1的第一个字符和Str2的第一个字符去比较，不符合，关键词向后移动一位 2.重复第一步，还是不符合，再后移 3.一直重复，直到Str1有一个字符与Str2的第一个字符符合为止 4.接着比较字符串和搜索词的下一个字符，还是符合。 5.遇到Str1有一个字符与Str2对应的字符不符合。 6.这时候，想到的是继续遍历Str1的下一个字符，重复第1步。(其实是很不明智的，因为此时BCD已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。) 7.怎么做到把刚刚重复的步骤省略掉？可以对Str2计算出一张《部分匹配表》，这张表的产生在后面介绍 8.已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数： 移动位数=已匹配的字符数-对应的部分匹配值 因为6-2等于4，所以将搜索词向后移动4位。 9.因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数=2-0，结果为2，于是将搜索词向后移2位。 10.因为空格与A不匹配，继续后移一位。 11.逐位比较，直到发现C与D不匹配。于是，移动位数=6-2，继续将搜索词向后移动4位。 12.逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数=7-0，再将搜索词向后移动7位，这里就不再重复了。 13.介绍《部分匹配表》怎么产生的 先介绍前缀，后缀是什么 “部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例， －”A”的前缀和后缀都为空集，共有元素的长度为0； －”AB”的前缀为[A]，后缀为[B]，共有元素的长度为0； －”ABC”的前缀为[A,AB]，后缀为[BC,C]，共有元素的长度0； －”ABCD”的前缀为[A,AB,ABC]，后缀为[BCD,CD,D]，共有元素的长度为0； －”ABCDA”的前缀为[A,AB,ABC,ABCD]，后缀为[BCDA,CDA,DA,A]，共有元素为”A”，长度为1； －”ABCDAB”的前缀为[A,AB,ABC,ABCD,ABCDA]，后缀为[BCDAB,CDAB,DAB,AB,B]，共有元素为”AB”，长度为2； －”ABCDABD”的前缀为[A,AB,ABC,ABCD,ABCDA,ABCDAB]，后缀为[BCDABD,CDABD,DABD,ABD,BD,D]，共有元素的长度为0。 14.”部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。 到此KMP算法思想分析完毕! 4.2.4代码实现： 关键是创建部分匹配表，当匹配出现不相等时不要回到原来的后一位，而是回到部分匹配表的后一位（匹配表字符中前一位和后一位相同时，部分匹配表加1） charAt()方法用于返回指定索引处的字符。索引范围为从0到length()-1。 难点：部分匹配表没有匹配到时： 5.贪心算法 5.1贪心算法介绍 1）贪心算法是指对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最优的算法 2）贪心算法得到的结果不一定是最优的结果（有时候是最优解），但是都是相对近似（接近）最优解的结果 5.2实践 5.3思路分析 使用贪心算法可以快速计算准备的值，使用贪心算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖地区全部地区的最小集合： 1）遍历所有的广播电台，找到一个覆盖了最多的地区的电台（此电台可能包含一些已经覆盖的电台） 2）将这些电台加入到一个集合中，想方法吧该电台覆盖的地区在下次比较时去掉。 3）重复第一步直到覆盖了全部地区 5.4图解 5.5代码实现： 6.普里姆算法（prim） 6.1算法的实例 6.2算法介绍 6.3图解： 6.4代码实现： 7.克鲁斯卡尔算法 7.1算法实例： 7.2算法介绍 1）克鲁斯卡尔（Kruskal）算法，是用来求加权连通图的最小生成树的算法。 2）基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路 3）具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止 7.3图解 第1步：将边 此时，最小生成树构造完成！它包括的边依次是： 根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：问题一对图的所有边按照权值大小进行排序。问题二将边添加到最小生成树中时，怎么样判断是否形成了回路。 问题一很好解决，采用排序算法进行排序即可。 问题二，处理方式是：记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 在将 (01)C的终点是F。(02)D的终点是F。(03)E的终点是F。(04)F的终点是F。 关于终点的说明： 1)就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 因此，接下来，虽然 7.4代码实现： 8.迪杰斯特拉（Dijkstra）算法 8.1算法实例 8.2算法介绍 迪杰斯特拉算法是典型的最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层层扩展（广度优先思想），直到拓展到终点为止。 8.3图解 8.4代码实现： 9.1算法介绍： 9.2算法分析与图解 1）设置顶点vi到顶点vk的最短路径已知为Lik顶点vk到vj的最短路径已知为Lkj，顶点vidaovj的路径为Lij，则vi到vj的最短路径为：min((Lik+Lkj),Lij),vk的取值为图中所有顶点，则可获得vi到vj的最短路径 2）至于vi到vj的最短路径Lik或者vk到vj的最短路径Lkj，是以同样的方式获得