算法说明
又叫折半查找,要求待查找的序列有序。
每次取中间位置的值与待查关键字比较;
如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程;
如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程。
直到查找到了为止,否则序列中没有待查的关键字。
示例代码
/**
* 二分查找算法实现,返回查找数据在数组的序号。
* @param array 数据
* @param num 需要查询的数据
* @return 数据序号
*/
public static int biSearch(int[] array, int num) {
int start = 0;
int end = array.length - 1;
int mid;
while(start <= end) {
mid = (start + end) / 2;
if(array[mid] == num) {
return mid;
} else if(array[mid] < num) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
调用示例:
public static void main(String[] args) {
int[] array = { 1, 2, 4, 6, 8, 9, 10, 11, 12, 34, 55};
int biSearch = biSearch(array, 9);
System.out.println(biSearch);
}
算法复杂度
因为二分查找是一半一半的找,所以每次查找之后都会把查找范围减半;
比如说在一个 1 - 8 的有序数组里面查找 8 也就是查找最坏情况。
在数组当中完成二分查找需要 log2n - 1 次;
也就是时间复杂度是 log2n (就是 log 以 2 为底 n 的对数)