详解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();
  }

来源：http://www.jianshu.com/p/8f5f8c04b531?utm_source=tuicool&utm_medium=referral