search - 这个算法的时间复杂度？

Question

需要帮助找出使用 Big-O 表示法的该算法的时间复杂度。干杯。

int binarySearch(int[] array, int key) {
    int lo = 0, mid, hi = array.length-1;
    while (lo <= hi) {
        mid = (lo + hi)/2;
        if (key < array[mid])
            hi = mid - 1;
        else if (array[mid] < key)
            lo = mid + 1;
        else return mid; // success
    }
    return -1; // failure
}

Answer 1

如果将数组中的元素数量加倍，则预期的步数会增加 1。因此它是 O(log(N)); 其中 log 以 2 为底。

Answer 2

如果您没有找到您搜索的内容，则每次您搜索的范围都会缩小两倍。例如，64 -> 32 -> 16 等。也就是说，您最多需要迭代 lb(n)。因此，运行时间为 O(lb(n))，其中 lb(n) 是 n 以 2 为底的对数。