你如何确定while循环的Big-O表示法？

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

Jon Skeet已经回答了这个问题.

在这里,我展示了如何以数学方式解决它.

因为在每个循环中我们将范围减半,在最坏的情况下,我们steps最多需要迭代.
我们如何计算steps数字？

"将范围减半"可表示为:范围/ 2 ^步

我们可以继续减半,直到range变为1.
所以等式是:range/2 ^steps = 1

解决方案:
lg(范围/ 2 ^步)= lg(1)
lg(范围) - 步骤*lg(2)= 0

steps = lg(range),其中lg是基数为2的对数.