二分法的插入问题

Question

二分法插入，运行的时候不出结果！感觉是数组中第一个插不进去的问题可是我不知道该如何解决，大家看看我该怎么改改。原程序如下:class OrderSort{
  private int[]a;
  private int end;
  public OrderSort(int size){
    a=new int[size];
    end=0;
  }
  public int getSize(){
    return end;
  }
  public void display(){
    for(int i=0;i<end;i++){
      System.out.println("a["+i+"]="+a[i]+"\t");
    }
    System.out.println();
  }
  public int find(int searchKey){ //二分查找
    int center; //中间位置
    int lowerbound=0,upperbound=end-1;
    while(true){
      center=(lowerbound+upperbound)/2;
      if(a[center]==searchKey)
      return center;
      else if(lowerbound>upperbound)
      return end;
      else{ //根据比较重新确定中间位置
        if(a[center]<searchKey)
        lowerbound=center+1;
        else
        upperbound=center-1;}
    }
  }  
/*  public void insert(int value){//线性插入
    int j;
    for(j=0;j<end;j++){
      if(a[j]>value)
      break;
    }
    for(int k=end;k>j;k--){
      a[k]=a[k-1];
    }
    a[j]=value;
    end++;
  } */
  public void insert(int value){ //二分插入
    int j,center;
    int lowerbound=0;
    int upperbound=end-1;
    
    while(true){
      center=(lowerbound+upperbound)/2;
      if(a[center]<value&&a[center+1]>value)
       {
for(j=end;j>center+1;j--){
           a[j]=a[j-1]; }
         a[center+1]=value;
         end++;  
       }
      else 
       {
        if(a[center]<value)
        lowerbound=center+1;
        else
        upperbound=center-1;
       }
    
      }
}
}
class Demo{
  public static void main(String []args){
    OrderSort arr=new OrderSort(10);
    arr.insert(100);
    arr.insert(300);
    arr.insert(40);
    arr.insert(30);
    arr.display();
    
  }
} 

Answer 1

帮你重写了二分算法.class OrderSort{
  private int[]a;
  private int end;
  public OrderSort(int size){
    a=new int[size];
    end=0;
  }
  public int getSize(){
    return end;
  }
  public void display(){
    for(int i=0;i<end;i++){
      System.out.println("a["+i+"]="+a[i]+"\t");
    }
    System.out.println();
  }
  public int find(int searchKey){ //二分查找
    int center; //中间位置
    int lowerbound=0,upperbound=end-1;
    while(true){
      center=(lowerbound+upperbound)/2;
      if(a[center]==searchKey)
      return center;
      else if(lowerbound>upperbound)
      return end;
      else{ //根据比较重新确定中间位置
        if(a[center]<searchKey)
        lowerbound=center+1;
        else
        upperbound=center-1;}
    }
  }  
/*  public void insert(int value){//线性插入
    int j;
    for(j=0;j<end;j++){
      if(a[j]>value)
      break;
    }
    for(int k=end;k>j;k--){
      a[k]=a[k-1];
    }
    a[j]=value;
    end++;
  } */
  public void insert(int value)
  {  //二分插入
   int left = 0;
   int right = end - 1;
  
   while(left <= right)
   {
   int mid = (left + right)/2;
   if (a[mid] > value)
   right = mid - 1;
   else
   left = mid + 1;
   }
   for (int i = end - 1; i >= left; i --) a[i + 1] = a[i];
   a[left] = value; 
   end ++;
  }
}
class Demo{
  public static void main(String []args){
    OrderSort arr=new OrderSort(10);
    arr.insert(100);
    arr.insert(300);
    arr.insert(40);
    arr.insert(30);
    arr.display();
    
  }
}