欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

详解Java数据结构和算法(有序数组和二分查找)

程序员文章站 2024-03-02 15:29:04
一、概述 有序数组中常常用到二分查找,能提高查找的速度。今天,我们用顺序查找和二分查找实现数组的增删改查。 二、有序数组的优缺点 优点:查找速度比无序数组快多了 缺...

一、概述

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

二、有序数组的优缺点

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

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

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

四、代码实现

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。