/*有序数组:主要是为了提高查找的效率
*查找:无序数组--顺序查找,有序数组--折半查找
*其中插入比无序数组慢
* */
public class MyOrderedArray {
private long[] arr;
private int items; public MyOrderedArray(int max) {
arr = new long[max];
items = 0;
} //数组中元素的个数
public int size(){
return items;
} //折半查找
public int find(long key){
int low = 0;
int high = items - 1;
int mid;//变化的
while(low <= high){
mid = (low + high) / 2;
if(key == arr[mid]){
return mid;
}
else if(key > arr[mid]){
low = mid + 1;
}
else if(key < arr[mid]){
high = mid - 1;
}
}
return -1;
} //插入元素
public void insert(long key){
int i; for( i = 0; i < items; i++){ //先找到位置
if(key < arr[i]){
break;
}
} for(int k = items;k>i; k--){ //移动元素
arr[k] = arr[k -1];
} arr[i] = key;//插入元素到找到的位置
items++;
} //删除元素--先判断找的位置合法--在判断
public boolean delete(long key){
int i = find(key);
if(i == items){
return false;
}
else{
for(int k = i; k < items; k++){
arr[k] = arr[k + 1];
}
items--;
return true;
}
} public void displayArray(){
for(int i = 0;i < items;i++){
System.out.print(arr[i] + " ");
}
System.out.println();
} }