1 时间复杂度
二分法查找的时间复杂度 T(n)=T(n/2)+O(1)所以T(n)=O(logn) 所有最坏的情况是logn,最好的情况是O(1).
2 代码实现
//二分法查找
private int binarySearchRank(int num, int[] array) {
int result = -1;
int start = 0;
int end = array.length-1;
while (start<end){
if(array[start] == num){
result = start;
break;
}
if(array[end] == num){
result = end;
break;
}
int middle = (start+end)/2;
if(array[middle]>num){
end = middle;
}else if(array[middle]<num){
start = middle;
}else {
result = middle;
break;
}
if(start+1==end){
result = -1;
break;
}
}
return result;
}
3 代码分析
可能存在这样一种情况，当所要查找的数值的大小在数组的最大值与最小值之间，但是又不存在。这时候会进入死循环。比如 数组为 [1，3，7，9，10]，num为4，这时候循环到sart=3，end=7，array[temp]=5，这时候num>array[temp]会一直执行下去。使用这种情况直接返回-1.也就是start=end-1的时候还没有找到目标值。
