数据结构与算法:有序数组和二分法查找
上次学习了数组,不过数组的赋值过程是无序的,是由输入的数值决定的,如下所示:
//插入
public void insert(int insertKey){
arr[cloum]=insertKey;
cloum++;
}
在实际应用中,经常用到有序数组。下面进行简单介绍,相比无序数组,就是在插入一个值的时候,需要先从头比较insertKey与数组中元素的大小,如果insertKey大,继续比较;如果出现arr[i]大的情况,则break,此时i即为插入的位置,i之后的元素全部后移一位。具体实现如下:
public void insert(int insertKey){
//1.先找到要插入的位置
int i;
for ( i= 0; i < cloum; i++) {
if(arr[i]>insertKey){
break; //找到要插入的位置就停止
}
}
//2.将数组插入位置之后的元素后移一位
for (int j =cloum; j >i; j--) {
arr[j]=arr[j-1];
}
arr[i]=insertKey;
cloum++;
}
下面是测试类:
public static void main(String[] args) {
MyOrderedArray arr=new MyOrderedArray();
arr.insert(1999);
arr.insert(75);
arr.insert(9);
arr.insert(2566);
arr.insert(123);
arr.insert(79);
arr.display();
arr.insert(99);
System.out.println();
arr.display()
}
结果显示:
9 75 79 123 1999 2566
9 75 79 99 123 1999 2566
下面讲讲查找算法,查找算法有顺序查找和二分法查找,所谓顺序查找,就是“傻瓜式”从头到尾一个一个去找,如果运气好的话,可能第一个就找到了,如果运气不好的话,直到找到最后一个才找到。如果数据量大的话,此时二分法查找就显示出优势了;
//使用二分法查找
public int binarySearch(int searchKey){
int index;
int pow=cloum;
int low=0;
while(true){
index=(low+pow)/2;
if(low > pow){
return -1;
}else{
if(arr[index]>searchKey){
pow=index-1;
}else if(arr[index]<searchKey){
low=index+1;
}else{
return index;
}
}
}
}
测试类:
System.out.println(arr.binarySearch(99));
System.out.println(arr.binarySearch(98));
结果显示:
9 75 79 123 1999 2566
9 75 79 99 123 1999 2566
3
-1