用Java二分法检索最大值
目录
1、二分法实现最大值的构想
2、用二分法寻找最大值的要点
3、二分法实现最大值java
代码:
结果:
4、另一个递归实现:
总结:
用二分法寻找最大值,与直接遍历相差不大,是主要使用的思路。 理解合并排序,找到最大值很简单。
1、二分法实现最大值搜索的构想1、分类的n个内容视为n个长度为1的顺序表
2 )将n个有序列表拆分成n/2个长度为2的有序列表
3、重复操作2,直到所有记录的n/2变为1或2,两个值可以进行比较
4 )判断分割后的有序列表,留下较大的值。
例如,有25、5、83、99、28、57、95、57、35、3这样的数字
分割和合并的过程如图所示。
2 )用二分法寻找最大值的要点从图中可以看出,分割比较容易,寻找最大值也很简单。
//定义比较两个数字大小的函数privatestaticintcompare(inta,int b )在system.out.println('number ) ' turn中为:(t ' ); 返回ab? a:b; } 1、找临界点。 因为比较至少需要两个值。
if(leftright-2 ) (/是两个值system.out.println (' left value : ' data arr [ left ] ' right value 3360 ' data arr [ right ] }
2 )获得左右两侧最大值进行比较
intmid=(leftright )/2; intleftmax=getmax(dataarr,left,mid ); intright max=get max (数据arr,mid 1,right ); system.out.println (' left max : ' left max ' right max ' right max ); ma
x = compare(leftMax, rightMax);3,二分法查找最大值java实现 代码: public class BinaryFindMax { private static int number=0; public static void main(String[] args) { int[] data = {25, 5, 83, 99, 28, 57, 95, 57, 35, 3 }; int max = getMax(data, 0, data.length - 1); System.out.println("max value: "+max); } /** * 用递归算法求数组中的最大值 * * @param dataArr 数组 * @param right 数组下标 * @param right 数组上标 * @return */ public static int getMax(int[] dataArr, int left, int right) { int max; if (left > right - 2) { // 小于等于两个值 System.out.println("left value: "+ dataArr[left] + " right value: "+ dataArr[right]); max = compare(dataArr[left], dataArr[right]); } else { int mid = (left + right) / 2; int leftMax = getMax(dataArr, left, mid); int rightMax = getMax(dataArr, mid + 1, right); System.out.println("left max: "+ leftMax + " right max "+ rightMax); max = compare(leftMax, rightMax); } return max; } // 定义一个比较两个数值大小的函数 private static int compare(int a,int b){ System.out.println("第"+(++number)+"趟进行比较:t"); return a>b?a:b; }} 结果: left value: 25 right value: 5第1趟进行比较:left value: 83 right value: 83第2趟进行比较:left max: 25 right max 83第3趟进行比较:left value: 99 right value: 28第4趟进行比较:left max: 83 right max 99第5趟进行比较:left value: 57 right value: 95第6趟进行比较:left value: 57 right value: 57第7趟进行比较:left max: 95 right max 57第8趟进行比较:left value: 35 right value: 3第9趟进行比较:left max: 95 right max 35第10趟进行比较: left max: 99 right max 95第11趟进行比较: max value: 99
4,另一种递归的实现: private static int max(int a,int b){ //定义一个比较两个数值大小的函数 return a>b?a:b;}// 用数组的第一个值作为初始值// 然后从数组的二个值开始,开始递进到最后一个值,然后回归,不断进行两两比较public static int getMaxNum(int[] arr,int startIndex){ if(startIndex==arr.length){ return arr[0]; } return max(arr[startIndex],getMaxNum(arr,startIndex+1));}public static void main(String[] args){ int array[]= {162,233,77,99,69,56,89,174,86,78}; System.out.print(getMaxNum(array,0));}
总结:
二分法查找最大值,本身不具有什么样的优势。主要是“分治”方法的一种应用。当作练习还是不错的。