Как вы определяете нотацию Big-O цикла while?

Question

Ниже приведена функция двоичного поиска.

int search(int a[], int v, int left, int right)
{
    while (right >= left)
    {
        int m = (left + right)/2;
        if (v == a[m]) 
            return m;
        if (v < a[m])
            right = m - 1;
        else left = m + 1;
    }
    return -1;
}

Как определить обозначение Big-O для этой функции?

Является ли эта функция поиска O (n), поскольку цикл while зависит от значения left ?

Answer 1

На каждом шаге диапазон значений уменьшается вдвое (примерно) - если вы начнете с right - left == 100, то на втором шаге будет 49, затем 24, затем 11 и т. Д.

Предполагая, что n = right - left, сложность O (log n). (Это зависит от значений как справа, так и слева.)

Answer 2

Джон Скит уже ответил на вопрос.

Здесь я покажу, как мы можем решить это математически.

Поскольку в каждом цикле мы делим диапазон пополам, в худшем случае нам потребуется steps итераций максимум.
Как мы вычисляем steps число?

«Половина диапазона» может быть выражена как: диапазон / 2 ^шагов

Мы можем продолжать делить пополам до тех пор, пока range не станет 1 .
Таким образом, уравнение: диапазон / 2 ^шагов = 1

Решение:
lg (диапазон / 2 ^шагов ) = lg (1)
lg (диапазон) - шаги * lg (2) = 0

шагов = lg (диапазон) , где lg - логарифм с основанием 2.