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

配列の要素数を 2 倍にすると、予想されるステップ数は 1 増加します。したがって、O(log(N)); です。ここで、log は底 2 です。

Answer 2

検索したものが見つからない場合は、検索するたびに、検索する範囲が 2 分の 1 になります。たとえば、64 -> 32 -> 16 などです。つまり、多くても lb(n) を反復する必要があります。したがって、実行時間は O(lb(n)) です。ここで、lb(n) は n の 2 を底とする対数です。