4
\$\begingroup\$
int binsearch(int x, int v[], int n) 
{
    int low, high, mid;
    low = 0;
    high = n-1;

    while (low <= high)
    {
        mid = (low+high)/2;

        if (x < v[mid])
            high = mid -1;
        else if (x > v[mid])
            low = mid + 1;
        else
            return mid; /* found match */
    }

    return -1; /* no match */ 
}

Exercise 3-1. Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside.) Write a version with only one test inside the loop and measure the difference in run-time.

This is the code I wrote :

int binsearch(int x, int v[], int n)
{
    int lh[2] = {0, n-1}, a[2] = {-1, 1}, mid;

    while (lh[0] <= lh[1])
    {
        mid = (lh[1] + lh[0])/2;

        if (x != v[mid])
            lh[x < v[mid]] = mid + a[x > v[mid]];
        else
            return mid;
    }

        return -1;
}

But they have about the same run-time? Why didn't removing one of the if statements reduce it?

\$\endgroup\$
2
  • 3
    \$\begingroup\$ You didn’t only remove one conditional, you also added indexing expressions. You were supposed to remove the the test “at the price of more tests outside”, which you didn’t do. \$\endgroup\$ Commented Aug 20, 2023 at 14:03
  • 3
    \$\begingroup\$ I think you can rewrite the code to do the lower bound search, then you need one more test after the loop. See here: codereview.stackexchange.com/a/286441/151754 \$\endgroup\$ Commented Aug 20, 2023 at 14:09

1 Answer 1

3
\$\begingroup\$

The performance is expected to be pretty much the same as the original.

In the most common case (x != v[mid]) the first code computes:

  • x < v[mid]
  • x > v[mid] (half the time, when the first condition is false)
  • Either high = mid -1 or low = mid + 1

The second code computes:

  • x != v[mid]
  • x < v[mid] and x > v[mid] for indexing lh and a respectively.

That hasn't reduced the complexity; in fact it's slightly increased it.

I think that what the exercise is looking for is that you can find the smallest value greater than or equal to x. Then after the loop, test whether that element actually is x.

I wouldn't expect to see a significant performance difference there either, but such a version would more reusable. It's often useful in binary search to locate the index where the sought element would be¹, so it makes sense to build search from such a version, and when we have that position, to test whether the value actually is present at that position.


A subtlety that's present in both versions looks like this:

       mid = (low+high)/2;

When low and high get large, their sum can be too big to represent in an int, and we get Undefined Behaviour. This means that literally anything is allowed to happen, and that's not a good thing.

The way to avoid this, given that we know low and high are both positive, is to compute mid by adding half the difference:

        mid = low + (high - low) / 2;

That's mathematically the same, but computationally very different (in particular, no overflow can occur).


¹ Frequently we want to insert a value if it's not already there - perhaps if we're building a cache, or counting occurrences.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.