详解Java数据结构和算法(有序数组和二分查找)
作者:临窗听雨 时间:2023-04-08 13:38:07
一、概述
有序数组中常常用到二分查找,能提高查找的速度。今天,我们用顺序查找和二分查找实现数组的增删改查。
二、有序数组的优缺点
优点:查找速度比无序数组快多了
缺点:插入时要按排序方式把后面的数据进行移动
三、有序数组和无序数组共同优缺点
删除数据时必须把后面的数据向前移动来填补删除项的漏洞
四、代码实现
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
标签:Java,有序数组,二分查找
0
投稿
猜你喜欢
DevExpress获取TreeList可视区域节点集合的实现方法
2023-09-18 15:42:05
使用@RequestParam设置默认可以传空值
2023-07-01 08:34:57
C#操作windows系统进程的方法
2023-06-09 05:11:45
springmvc实现自定义类型转换器示例
2021-09-29 23:46:53
c语言版本二叉树基本操作示例(先序 递归 非递归)
2023-03-17 23:40:25
java 重定义数组的实现方法(与VB的ReDim相像)
2022-08-09 23:09:25
举例讲解Java编程中this关键字与super关键字的用法
2023-03-09 01:46:02
关于C语言动态内存管理介绍
2022-07-31 17:05:32
SpringBoot项目集成Swagger和swagger-bootstrap-ui及常用注解解读
2023-03-17 06:30:20
SpringBoot选择自有bean优先加载实现方法
2023-05-21 06:22:39
Java中线程状态+线程安全问题+synchronized的用法详解
2023-08-23 08:38:07
Android在linux下刷机教程
2023-09-03 17:21:04
Mac Android Studio 3.0 Terminal 中文乱码问题处理
2023-08-12 13:42:09
Java由浅入深带你了解什么是包package
2022-04-17 02:33:39
android动态壁纸调用的简单实例
2023-11-17 05:43:28
SpringBoot整合Security安全框架实现控制权限
2022-10-03 14:37:15
C# SQLite执行效率的优化教程
2021-07-11 00:11:41
通过C#实现自动售货机接口
2023-12-16 00:15:36
Android 10 启动之servicemanager源码解析
2023-05-16 15:04:53
Android将项目导出为Library并在项目中使用教程
2022-01-31 14:57:17