二进制搜索算法的时间复杂性是什么?

Question

我正在研究二进制搜索树，我写了一种在数组Java列表中执行二进制搜索的方法。但是，我正在尝试确定该算法的时间复杂性。但是我是这个话题的新主题，我不确定如何使用大o符号来弄清楚时间复杂性。

public <T extends Comparable<T int binarySearch(T[] array,T target) {
    int first = 0, last = array.length-1; // initially search in the whole array
    while (first <= last) {// still at least one element in search space
                           // calculate median index, halfway between first and last indices. . .
        int median = (first+last)/2;
        // . . . and get the value there
        int comparison = array[median].compareTo[target];
        if (comparison == 0) {// target value found
            return median;
        } else if (comparison > 0) {// median value is larger than target
            last = median-1; // search further in lower half of search space
        } else {// median value is smaller than target
            first = median+1; // search further in upper half of search space
        }
    }
    return -1; // ran out of search 

Answer 1

复杂性是 o(logn(。

wikipedia