Java二分法查找

在算法与数据结构中，二分法查找是一种最简单的入门算法，它用于在已经排序好的序列中查找元素。

例子：{1,2,3,4,5,6,7,8,9,10}这样的数组中找出元素10的索引。

如果用单纯的for循环的话

public static int searchIndex(){
int[] a = {1,2,3,4,5,6,7,8,9,10};
                int n = 10;
                int index = -1;
for(int i=0;i<a.length;i++){
if(n == a[i]){
index = i;
}
}
return index;
}

这样我如果要找10的话他就会循环10次，如果数组过大的循环就会很大。这里用二分法的方法效率就很高

public static int searchIndex(){
//查找N在数组a中的位置
int n = 10;

int[] a = {1,2,3,4,5,6,7,8,9,10};
int index = -1;
int start = 0;
int end = a.length;
while(start<=end){
int avg = (start + end)/2;
if(n == a[avg]){
index = avg;
break;
}else if(n > a[avg]){
start = avg + 1;
}else if(n < a[avg]){
end = avg -1;
}
}
return index;
}

用二分法查找只循环了4次，它是借助的要查找数组的顺序特点来排序的。