自定义有序数组_用二分法查找数据
程序员文章站
2024-03-17 15:30:28
...
/**
* java 模拟有序数组
* @author zm
*/
public class MyOrderArray {
private int size; // 实际个数
private int[] arr;
private int max; // 数组最大长度
public MyOrderArray(){
arr = new int[10];
max = 10;
}
public MyOrderArray(int size){
arr = new int[size];
max = size;
}
// 升序增加
public void insert(int val){
int i;
for(i=0; i<size;i++){
if(val < arr[i]){ // 记录插入点
break;
}
}
// 插入数据时, 移动数据要从后开始移动
for(int j=size; j>i;j--){
arr[j] = arr[j-1];
}
arr[i] = val;
size++;
}
// 展示数组内数据
public void display(){
if(this.size > 0){
System.out.print("[");
for(int i=0; i<size; i++){
System.out.print(arr[i] +" ");
}
System.out.print("]");
}else{
System.out.print("[]");
}
}
// 二分法查找数据
public int binarySearch(int val){
int low = 0;
int mid = 0;
int high = size;
while(true){
mid = (low + high) / 2;
if(high < low){
return -1;
}else{
if(arr[mid] == val){
return mid;
}else{
if(arr[mid] < val){
low = mid + 1;
}
if(arr[mid] > val){
high = mid - 1;
}
}
}
}
}
public static void main(String[] args) {
MyOrderArray array = new MyOrderArray();
array.insert(90);
array.insert(30);
array.insert(80);
array.insert(10);
array.display(); // [10 30 80 90 ]
System.out.println("");
int index = array.binarySearch(31);
System.out.println(index);
}
}
上一篇: POJ 3258 -- River Hopscotch(二分)
下一篇: 关押罪犯(分多个集合!!)