从数组中查找特定数据的最简单办法就是遍历数组中所有的元素,这种查找方式称为线性查找。对于小型数组或者是没有经过排序的数组的可以采用这样的办法,对于已经排序的数组可以采用高效的二叉查找算法。该算法查找数组中位于中间位置的元素,并将其与查找值比较,如果两者相等就返回该元素的索引,否则将问题化简为查找元素的一半来处理。
class ArrayFinder{
public static void print(int[] array,int middle){
for(int i=0;i<array.length;i++){
System.out.print(array[i]);
if(i == middle)System.out.print("*");
System.out.print(" ");
}
System.out.println();
}
public static int indexOf(int[] array,int value){
int low = 0;
int high = array.length-1;
int middle;
while(low <= high){
middle = (low + high)/2;
print(array,middle);
if(array[middle] == value) return middle;
if(value < array[middle]) //要比较的值比中间值小
high = middle +1;
else
low = middle - 1;
}
return -1;
}
public static void main(String[] args){
int[] array = new int[]{1,2,3,4,6,9,12};
System.out.println("location of 13: "+indexOf(array,4));
}
}
Result :
D:\jcode>javac ArrayFinder.java
D:\jcode>java ArrayFinder
1 2 3 4* 6 9 12
location of 13: 3