算法（四）二分法查询

二分法讲解：

二分法的核心便是不断的缩小区间。要求的数大于底边则向上收缩区间，反之则向下。 以下是两个简单的案例来帮助大家理解和应用。基本上所有有序的数组都能够使用二分法写出想要的功能。

import java.util.Arrays; public class Demo1 { public static void main(String[] args) { //初始化一个静态数组 int [] values={3,72,8,5,9,150,27,85,94,66,21,45}; //排序数组，二分法查找的前提数组是有序的（按小到大，从左往右排） Arrays.sort(values); System.out.println(Arrays.toString(values)); //指定要查找的数 int value=8; //查找数的下标 int index=new Demo1().dichotomy(values, value); //System.out.println("你要查找的数在数组中的下标为:"+index); } /* * 参数values，查询数组。参数value，要查询的值。 */ private int dichotomy(int [] values,int value) { //变量base=底边 int base=0; //变量top=顶边 int top=values.length-1; while(base<=top){ //middle=中间 int middle=(top+base)/2; System.out.println("此次循环中间的数为:"+values[middle]+",下标为:"+middle); //查询到了就返回下标 if(value==values[middle]){ return middle; } //如果要查询的数比现在中间的数小，那么顶边=middle-1; if(value<values[middle]){ top=middle-1; } //如果要查询的数比现在中间的数小，那么底边=middle+1; if(value>values[middle]){ base=middle+1; } } //没找的返回-1 return -1; } }

结果如下：

实例问题

2. 获取数组最大值和最小值操作：利用Java的Math类的random()方法，编写函数得到0到n之间的随机数，n是参数。并找出产生50个这样的随机数中最大的、最小的数，并统计其中>=60的有多少个。

提示：使用 int num=(int)(n*Math.random());获取随机数。（题目出自http://www.sxt.cn/Java_jQuery_in_action/seven-task.html）

以下是本人提供的优化解法：

public class Demo3 { public static void main(String[] args) { Demo3 d3= new Demo3(); Scanner input=new Scanner(System.in); System.out.print("请输入准备生成多少个随机数:"); int numbers=input.nextInt(); System.out.print("请输入生成随机数的最大范围:"); int maxRange=input.nextInt(); int values[]=d3.initialize(numbers, maxRange); //排序数组 Arrays.sort(values); System.out.println(Arrays.toString(values)); //输出最大 System.out.println("最大随机数:"+values[values.length-1]); //输出最小 System.out.println("最小随机数:"+values[0]); //输出大于60 int index=d3.greaterToValue(values, 60); System.out.println("数组中大于60的数:"); //输出下标 System.out.println("大于60的下标为:"+index); if(index==-1){ return; } for (int i = index,j=0; i < values.length; i++,j++) { if(j==0){ System.out.print("\n"); } System.out.print(values[i]+" "); } } //初始化数组 private int[] initialize(int nums,int maxRange){ int values[]=new int[nums]; for (int i = 0; i < values.length-1; i++) { values[i]=(int)(Math.random()*maxRange); } return values; } //二分法查询大于60的数 private int greaterToValue(int [] values,int value){ //底边 int base=0; int middle=0; //顶边 int top=values.length-1; while(base<=top){ //中间的数 System.out.println("base:"+base+"|top:"+top); middle=(base+top)/2; //middle左边一个小于60&&middle大于等于60跳出循环，返回下标 if(values[middle-1]<value&&values[middle]>=value){ return middle; } //middle大于等于60,顶边界限为middle-1 if(value<=values[middle]){ top=middle-1; } //middle小于60，底部界限为middle+1 if(value>values[middle]){ base=middle+1; } } return -1; } }

运行结果：

查询一个两百的数组仅仅只需要6次循环，效率可观。