利用二分比较法,快速找到元素插入位置

package Test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Test {

	private int getBisearchElement(double dou[],int size){
		if(size==0){
			size = dou.length;
		}
		if(size==1){
			return 0;
		}
		return size/2;
	}
	
	private double getDouble() throws IOException{
		InputStreamReader reader = new InputStreamReader(System.in);
		BufferedReader input = new BufferedReader(reader);
		String s = input.readLine();
		return Double.parseDouble(s);
	}
	
	/**
	 * 比如:
	 * d1=0.12951463 d2=0.08425 1
	 * d1=0.12951463 d2=0.2516 -1
	 */
	private int compare(double d1,double d2){
		return Double.compare(d1, d2);
	}
	
	private double getDoubleElement(double dou1[],int size){
		return dou1[size];
	}
	
	/**
	 * 作用:利用二分比较法,快速找到元素插入位置
	 * 参数:dou1 数组;d2 插入元素;startlocation 前次数组endlocation下标;endlocation 数组endlocation下标
	 * 具体说明:第一步：判断两个Double元素哪个比较大,结果为1或者-1.
	 * 首先分析结果为1的情况:
	 *    无非就是挨靠与无挨靠的问题.举例说明数组[0.05550627,0.065414764,0.07849772...],0.05550627,0.065414764
	 *    是挨靠,0.05550627和0.065414764是无挨靠.概念清楚了,那么根据什么知道它们有无挨靠？依据就是形参startlocation
	 *    和endlocation.如果是无挨靠,那么就要进行如下公式：当前数组(endlocation)下标-前次数组(endlocation)下标=插入元素
	 *    适合的范围;插入元素适合的范围/2=从适合的范围的中间开始.
	 */
	private int compare(double dou1[],double d2,int startlocation,int endlocation){			
		int size = 0;
		double d1 = getDoubleElement(dou1,endlocation);
		int icomparser = compare(d1, d2);
		if(icomparser==1){//d1大,d2属于左边  第一步
			if(startlocation==endlocation-1){//它们俩是压着
				if(startlocation==0){
					if(compare(getDoubleElement(dou1,startlocation), d2)==1){
						size = 0;
					}else{
						size = 1;
					}
				}else{
					size = endlocation;
				}
				this.startlocation = endlocation;
			}else{
				int newsize = endlocation - startlocation;
				newsize = newsize/2;
				size = newsize + startlocation;
			}
		}else if(icomparser==-1){//d1小,d2属于右边 第一步
			int newsize = dou1.length-endlocation;
			if(newsize==1){//等于1,说明已经到了最后一个元素
				if(compare(getDoubleElement(dou1,endlocation), d2)==1){
					size = endlocation+1;
				}else{
					size = endlocation;
				}
			}else{
				newsize = newsize/2;
			}
			size = newsize + endlocation;
			this.startlocation = endlocation;
		}else if(icomparser==0){
			size = endlocation;
			this.startlocation = endlocation;
		}
		return size;
	}
	
	//插入位置
	public int location(Double d2) throws IOException{
		int dou1length = this.dou1length-1;	
		endlocation = getBisearchElement(dou1,0);
		while(endlocation<=dou1length){
			endlocation = compare(dou1 , d2 , startlocation , endlocation);	
			if(startlocation==endlocation||endlocation==0){
				break;
			}
		}
		return endlocation;
	}
	
	//插入指定的位置
	public void insertlocation(int location,double d1) throws Exception{
		if(location==dou1length){
			int i = size;
			int length = location-i;
			while(i>=2){
				dou1[length] = dou1[length+1];
				i--;
				length = location-i;
			}
			dou1[location-1] = d1;
			
		}else{
			int i = location;
			int length = location-i;
			int ilength = location-1;
			while(length!=ilength){
				dou1[length] = dou1[length+1];
				i--;
				length = location-i;
			}
			dou1[location-1] = d1;
		}
	}
	
	private static int startlocation = 0,endlocation = 0;
	private static int size = 6;
	private static double dou1[] = new double[size];
	
	private static int dou1length = 0;
	
	static{
		dou1length = dou1.length;
	}
	
	public static void main(String[] args) throws Exception {
		Test test = new Test();
		double d2 = test.getDouble();
		int location = test.location(d2);
		test.insertlocation(location, d2);
		startlocation = 0;
		endlocation = 0;
		d2 = test.getDouble();
		location = test.location(d2);
		test.insertlocation(location, d2);
		startlocation = 0;
		endlocation = 0;
		d2 = test.getDouble();
		location = test.location(d2);
		test.insertlocation(location, d2);
		startlocation = 0;
		endlocation = 0;
		d2 = test.getDouble();
		location = test.location(d2);
		test.insertlocation(location, d2);
		startlocation = 0;
		endlocation = 0;
		d2 = test.getDouble();
		location = test.location(d2);
		test.insertlocation(location, d2);
		startlocation = 0;
		endlocation = 0;
		for(int i=0;i<dou1length;i++){
			System.out.print(dou1[i]+",");
		}
	}

}