java – 试图证明二进制搜索的复杂性是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,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,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).

我的假设是,我可能错了计算电话.有人能告诉我哪里错了吗？