”二分查找“算法的时间复杂度

算法的时间复杂度无非就是for、while等包含起来的基本运算单元的循环次数

1、二分查找

二分查找(binary search),也称作折半查找(half-interval search),每次划分一半进行下一步搜索,所以时间复杂度无非就是while循环的次数!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//二分查找 Java 实现
public static int binarySearch(Integer[] srcArray, int des) {
int low = 0;
int high = srcArray.length - 1;

while ((low <= high) && (low <= srcArray.length - 1)
&& (high <= srcArray.length - 1)) {
int middle = (high + low) >> 1;
if (des == srcArray[middle]) {
return middle;
} else if (des < srcArray[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}

2、时间复杂度

比如:总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。
由于n/2^k取整后>=1,即令n/2^k=1,
可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O()=O(logn)

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2019 iTimeTraveler All Rights Reserved.

访客数 : | 访问量 :