Optimized Binary Search

[funprogrammer]

I was looking at some code for binary search and its optimized version on geeksforgeeks website.

The following piece of code was provided

Normal Binary Search:

// Returns location of key, or -1 if not found
int BinarySearch(int A[], int l, int r, int key)
{
    int m;
 
    while( l <= r )
    {
        m = l + (r-l)/2;
 
        if( A[m] == key ) // first comparison
            return m;
 
        if( A[m] < key ) // second comparison
            l = m + 1;
        else
            r = m - 1;
    }
 
    return -1;
}

Optimized Binary Search Code:

int BinarySearch(int A[], int l, int r, int key)
{
    int m;
 
    while( r - l > 1 )
    {
        m = l + (r-l)/2;
 
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
 
    if( A[l] == key )
        return l;
    else
        return -1;
}

The author claims, we are reducing comparison by 1 in the while loop. I can see that in the while loop but I don't think it looks correct. Didn't we just move the comparison to outside the while loop in another if, else loop? Is this really an optimized solution?

[JLBorges]

The second 'optimised' version would be marginally faster if the item being searched for is not in the array.

It would perform marginally slower if the item being searched for is bang in the middle of the array.

These are the extreme cases; you might want to try and work out the details for the intermediate cases.

[coder777]

The second one is probably faster (depends on the optimization of the compiler). You can find both algorithm here:

https://en.wikipedia.org/wiki/Binary_search_algorithm

The first: Chapter 'Iterative'
The second: Chapter 'Deferred detection of equality'

[funprogrammer]

Thanks @JLBorges & @coder777.