Java数据结构和算法（有序数组和二分查找）

一、概述

有序数组中常常用到二分查找，能提高查找的速度。今天，我们用顺序查找和二分查找实现数组的增删改查。

二、有序数组的优缺点

优点：
查找速度比无序数组快多了
缺点：
插入时要按排序方式把后面的数据进行移动

三、有序数组和无序数组共同优缺点

删除数据时必须把后面的数据向前移动来填补删除项的漏洞

四、代码实现

public class OrderArray {
    
     private int nElemes; //记录数组长度
     
     private long[] a;
     
     /**
      * 构造函数里面初始化数组 赋值默认长度
      *
      * @param max
      */
     public OrderArray(int max){
          this.a = new long[max];
          nElemes = 0;
     }
     
     //查找方法 (二分查找)
     public int find(long searchElement){
         int startIndex = 0;
         int endIndex = nElemes-1;
         int curIn;
         while(true){
             curIn = (startIndex + endIndex)/2;
             if(a[curIn]==searchElement){
                 return curIn; //找到
             }else if(startIndex>endIndex){ //沒有找到
                 return nElemes; //返回大于最大索引整数
             }else{ //还要继续找
                 if(a[curIn]<searchElement){
                     startIndex = curIn + 1; //改变最小索引
                 }else{  //往前找
                     endIndex = curIn -1;
                 }
             }
             
         }
     }
     
     
     //插入元素（线性查找）
     public void insert(long value){
          int j;
          for(j=0;j<nElemes;j++){
              if(a[j]>value){
                  break;
              }
          }
          for(int k=nElemes;k>j;k--){
              a[k] = a[k-1];
          }
          a[j] = value;
          nElemes++;
     }
     
     //删除数据项
     public boolean delete(long value){
         int j = find(value);
         if(j==nElemes){
             return false; //没找到
         }else{
             //所有元素往前移动一位
             for(int k=j;k<nElemes;k++)
             a[k] = a[k+1];
             
             nElemes--;
             return true;
         }
     }
     //展示的方法
     public void display(){
         for(int i=0;i<nElemes;i++){
             System.out.print(a[i]+" ");
         }
     }
     
     public int size(){
         return nElemes;
     }
}

五、测试

 public static void main(String[] args) {
         int max = 100;
         OrderArray oa = new OrderArray(max);
         oa.insert(12);
         oa.insert(14);
         oa.insert(90);
         oa.insert(89);
         oa.insert(87);
         oa.insert(88);
         oa.insert(67);
         oa.display();
         int searchkey = 90;
         if(oa.find(searchkey)!=oa.size()){
             System.out.println("found"+searchkey);
         }else{
             System.out.println("not found");
         }
         oa.delete(88);
         oa.delete(90);
         oa.delete(89);
         oa.display();
     }