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

问题：《编程之美》，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");
  
 }
}