折半查找基本要求:待查找数组必须是有序的(以下代码是基于递增有序)
/**
* 折半查找
* @param a 给定数组
* @param low
* @param high
* @param k 需要查找的数字
* @return
*/
public static int bSearch(int[] a, int low, int high, int k){
int mid;
//循环
while(low<=high){
mid = (low+high)/2; // 取表中间位置
if(a[mid]==k){
return mid;
}else if(a[mid]>k){ // 说明需要在a[low...mid-1] 中查找, 即左边查找
high = mid-1;
} else{ // 说明需要在a[mid+1...high] 中查找, 即右边查找
low = mid +1;
}
}
return -1; // 找不到返回-1
}
测试如下:
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5};
System.out.println(bSearch(a, 0, a.length-1, 5));
}
输出结果:
4
时间复杂度:O(logn)
平均查找长度:log(n+1)-1