我正在尝试证明二分搜索的复杂度。维基百科上说,最坏情况下的时间复杂度是O(log(n))。这意味着:
如果我的数组有16个元素,log(16)等于4。我应该最多调用4次才能在数组中找到元素。
我的Java代码:
class Main{
int search(int[] array, int number, int start, int end) {
System.out.println("Method call");
int half = (end - start) / 2;
if (array[start + half] == number) {
return array[start + half];
}
if (array[start + half] < number) {
return search(array, number, start + half, end);
} else {
return search(array, number, start, end - half);
}
}
public static void main(String[] args) {
int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
for (int i : array) {
System.out.println(i);
new Main().search(array, i, 0, array.length);
}
}
}
Ideaone代码:http://ideone.com/8Sll9n
输出结果如下:
1
Method call
Method call
Method call
Method call
Method call
2
Method call
Method call
Method call
Method call
3
Method call
Method call
Method call
4
Method call
Method call
Method call
Method call
5
Method call
Method call
6
Method call
Method call
Method call
Method call
7
Method call
Method call
Method call
8
Method call
Method call
Method call
Method call
9
Method call
10
Method call
Method call
Method call
Method call
11
Method call
Method call
Method call
12
Method call
Method call
Method call
Method call
13
Method call
Method call
14
Method call
Method call
Method call
Method call
15
Method call
Method call
Method call
16
Method call
Method call
Method call
Method call
除了搜索数字1以外,一切都很好。这里有5个"方法调用",意味着5大于log(16)。
我的假设是,可能我在计算调用次数时出错了。有人可以告诉我我哪里错了吗?