详解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(); }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。