How do you determine the Big-O notation of a while loop?

Question

Below is a binary search function.

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;
}

How do I determine the Big-O notation for this function?

Is this search function O(n) since the while loop is dependent on the value of left?

Answer 1

In each step, the range of values halves (roughly) - if you start with right - left == 100, then at the second step it will be 49, then 24, then 11 etc.

Assuming n = right - left, the complexity is O(log n). (It's dependent on the values of both right and left.)

Answer 2

Jon Skeet already answered the question.

Here I show how we can solve it mathematically.

Since in each loop we halve the range, in the worst case we'll need steps iterations at most.
How do we calculate the steps number?

"Halving the range" can be expressed as: range / 2^steps

We can continue halving until range becomes 1.
So the equation is: range / 2^steps = 1

Solution:
lg(range / 2^steps) = lg(1)
lg(range) - steps*lg(2) = 0

steps = lg(range), where lg is the logarithm with base 2.

Answer 3

BIG-OH IS 0(Lgn)