Is this implementation of binary search correct?

Question

Is this implementation of binary search correct? Any special or edge cases that I missed out? Maybe it should be optimized for elements that are less than the first element of the array or greater than the last element?

bool binarySearch (int* array, int arraySize, int element)
{
    if ( arraySize == 0 )
    {
        return false;
    }

    int startPos = 0;
    int endPos = arraySize;
    while ( true )
    {
        int spanSize = endPos - startPos;
        if ( spanSize == 1 )
        {
            break;
        }
        int pivotPos = startPos + (spanSize >> 1);
        if ( element < array[pivotPos] )
        {
            // go left
            endPos = pivotPos;
        }
        else
        {
            // go right
            startPos = pivotPos;
        }
    }
    return element == array[startPos];
}

http://ideone.com/bcGsWG

Answer 1

I believe it works correctly, but I'm not enthused about the style.

A few points in no particular order:

Array indices should be size_t rather than int.

I really dislike loops of the form:

while (true) {
    if (something) break;
    do_real_loop_body();
}

I'd rather see the condition for exiting the loop written into the loop condition itself.

In this case, I'd also rather see a for loop than a while loop. We need to do some initialization, a test on every iteration, and update some variables ever iteration. When we have all three elements of the for loop, we might as well use it as simulate it on our own.

Although I know some misguided people agree, it's also generally best to avoid using braces when (for example) each leg of your if statement is only controlling a single statement.

Incorporating all these, we end up with a function that looks more like this:

bool binarySearch(int* array, size_t endPos, int element) {
    if (endPos == 0)
        return false;

    size_t startPos = 0;
    for (size_t pivotPos = endPos/2; 
        endPos-startPos != 1; 
        pivotPos = startPos + (endPos - startPos) / 2)
    { 
        if (element < array[pivotPos])
            endPos = pivotPos;
        else
            startPos = pivotPos;
    }
    return element == array[startPos];
}

The next step would be to make it generic, working with iterators so it can deal with different containers and different types in those containers. For that we could end up with something closer to this:

template <class Iter, class T>
bool bfind(Iter left, Iter right, T val) {
    Iter o = right;
    while (left < right) {
        Iter middle = left + (right - left) / 2;
        if (*middle < val)
            left = middle + 1;
        else
            right = middle;
    }
    return left != o && *left == val;
}

Interestingly, the generic version is not only more versatile, but also somewhat simpler.