分治算法（二）--》数组中的第二小值

问题：《编程之美》，page170. 寻找数组中的第二小数

public class FindSecondMin {

	/**
	 * @author:lilywangcn
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array=new int[]{12,34,54,43,23,11,10,9,9,10,9,10};
		try{
			System.out.println("min2 is " + array[merge(array,0,array.length-1)[1]]);
			System.out.println("min2 is " +directCompare(array));
		}catch(Exception e){
			e.printStackTrace();
		}
	}
		/*
		 * 算法设计：
		 
	init:min=min2=array[0];
	
	case: array[i]<min=min2  min2=min, min=array[i];  result: min<min2
	case: array[i]<min<min2  min2=min,min=array[i];   result:min<min2
	case: min=min2<=array[i]  min2=array[i];           result:min<=min2
	case: min=array[i]<min2  min2=array[i];			  result:min2=min
	case: min<array[i]<min2  min2=array[i]; 		  result:min<min2
	case: min<min2=array[i]  不处理。			      result: min<min2
	case：min<min2<array[i]  不处理。                                               result: min<min2
		 */
	public static int directCompare(int[] array) throws Exception{
		check(array);
		int min2;
		int min;
		if(array[0]>array[1]){
			min2=array[0];
			min=array[1];
		}else{
			min2=array[1];
			min=array[0];
		}
		for(int i=2; i<array.length;i++){
			if(min>array[i]){
				min2=min;
				min=array[i];
			}else { //min<=array[i]
				if(min==min2){  //min=min2<=array[i]
					min2=array[i];
				}else{          //min<min2,min2>array[i]
					if(min2>array[i]&&min!=array[i]){
						min2=array[i];
					}
				}
			}
		}
		return min2;
	}

也如下分析：
已知有min<min2,min，min2，array[i]的有序排列结果有三种
(1)(array[i],min,min2);需要对(min,min2)进行: min2=min，min=array[i]可以得到。处理条件：array[i]<min
(2)(min,array[i],min2);需要对(min,min2)进行: min2=array[i]可以得到。处理条件：min<array[i]<min2或min=min2<array[i]
(3)(min,min2,array[i]),不需要对(min,min2)做任何处理。条件：以上条件的反面
因此for循环也可如下：
for(int i=2; i<array.length;i++){
if(min>array[i]){
				min2=min;
				min=array[i];
			}
			
			if((min<array[i]&&array[i]<min2) || (min==min2 && min2<array[i])){
				min2=array[i];
			}
}

	/*
	 * 归并过程
	 * left:(a1,a2),right:(b1,b2)
	 * if(a1<a2<=b1<=b2) return left;
	 * if(b1<b2<=a1<=a2) return right;
	 * 否则最小，第二小值分布在两边。
	 * if(a1<b1)  min=a1,min2=b1;
	 * if(a1>b1) min=b1,min2=a1;
	 * if(a1=b1) case: a2=b2  return left;
	 *           case: a2>b2  return a1,b2;
	 *           case: a2<b2  return a1,a2;
	 */
	public static int[] merge(int[] array,int start,int end) throws Exception{
		check(array);
		int[] mins=new int[2];
		if(end-start==1){
			if(array[start]>array[end])
			{
				mins[0]=end;
				mins[1]=start;
			}else{
				mins[0]=start;
				mins[1]=end;
			}
			return mins;
		}
		if(start==end){  
            mins[0]=mins[1]=start;  
            return mins;  
        }else{
			int[] left=merge(array,start,(start+end)/2);
			int[] right=merge(array,(start+end)/2+1,end);
			
			if(array[left[1]]<=array[right[0]]&& array[left[0]]!=array[left[1]])  return left;
			if(array[right[1]]<=array[left[0]]&& array[right[0]]!=array[right[1]])  return right;
			if( array[left[0]]<array[right[0]]){
				mins[0]=left[0];
				mins[1]=right[0];
			}else if(( array[left[0]]==array[right[0]])){
				if(array[right[0]]==array[right[1]]) return left;
				mins[0]=left[0];
				if(array[left[1]]<array[right[1]]){
					mins[1]=left[1];
				}else{
					mins[1]=right[1];
				}
			}else{
				mins[0]=right[0];
				mins[1]=left[0];
			}
		
			return mins;
		}
		
	}
	
	public static void check(int[] array) throws Exception{
		if(array.length==0 ) 
			throw new Exception("error,the array is empty");
		else 
			if(array.length==1) throw new Exception("error,the array size is one");
		
	}
}