二分法查询

 

public class Dichotomy {

 

public static void main(String[] args) {

int[] array=new int[100000];

for(int i=0;i<100000;i++){

array[i]=(i+10);

}

int point=find(array,99998);

System.out.println("返回数组的索引："+point);

System.out.println("对比查询结果（查询条件：99998，结果："+array[point]+")");

}

/**

* 二分法，当一个数据集合为有序的时候可以使用二分法来查询，

* 这里在一个数组中查询一个值，并返回它的索引(这里假设数组为升序排序，并且值都不等)

*/

public static int find(int[] array,int param){

int firstPoint=0;

int lastPoint=(array.length-1);

int point;

int i=1;

while(true){

point=(firstPoint+lastPoint)/2;

if(array[point]==param){

return point;

}else if(firstPoint>lastPoint){

return -1; //没有查询结果，返回-1

}else{

if(array[point]>param){

lastPoint=point-1;

}else{

firstPoint=point+1;

}

}

System.out.println("循环次数："+i++);

}

}

}

/*

  打印结果：

  循环次数：1

循环次数：2

循环次数：3

循环次数：4

循环次数：5

循环次数：6

循环次数：7

循环次数：8

循环次数：9

循环次数：10

循环次数：11

循环次数：12

循环次数：13

循环次数：14

循环次数：15

返回数组的索引：99988

对比查询结果（查询条件：99998，结果：99998)

 */