Unable to implement upper_bound() properly

Question

I struggle a lot with binary search implementations, especially

• how to choose high and low (or r and l)
• whether to put equality sign in while loop condition or not
• whether to update r=mid or r=mid-1

I was trying to implement upper_bound from STL, but couldn't get the correct answer. Here is my code.

#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n+2);
    // adding 0 in front to avoid out of bounds error 
    // when looking for a[m-1]
    a[0]=0;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    // adding a big element at the end to return that index
    // when required element is greater than all elements
    a[n]=INT_MAX;

    // q queries for testing purposes
    int q;
    cin >> q;
    while(q--){
        // we return m-1 at the end, so l and r capture 
        // all possible outputs, inclusive bounds
        int l=1, r=n+1, m;
        int val;
        cin >> val;

        // always confused whether to put in 
        // the equality sign or not
        while(l<=r){
            m=(l+r)/2;
            // break when the required element is found
            if(a[m]>val && val>=a[m-1])
                break;
            else if(val>a[m])
                l=m+1;
            else
                r=m-1;
        } 
        cout << m-1 << " ";
    }

    return 0;
}

Sample input for testing:

7
3 6 8 10 11 14 22
6
0 10 1 3 15 28

Expected output if I had used upper_bound from STL:

0 4 0 1 6 8

Got output for my implementation

0 2 0 1 6 6

I am getting the wrong output and I can't figure out why. Any simplifications I could keep in mind to avoid such implementation errors or to ease my understanding of how to write code for binary search?

Answer 1

To design correct binary search function, don't try to guess the solution, it's hard to get it right. Use the method of loop invariants. Suppose, we want to implement upper_bound from the Standard library:

template<class It, typename T>
It upper_bound(It first, It last, const T& value);

According to the specification of upper_bound, we are looking for the transition point pt, such that in the range [first, pt) all elements have values <= value, and in the range [pt, last) all elements have values > value.

Let's introduce two iterators (pointers) left and right with the loop invariants:

• in the range [first, left) all elements have values <= value,
• in the range [right, last) all elements have values > value.

These ranges represent elements examined so far. Initially, left = first, and right = last, so both ranges are empty. At each iteration one of them is expanded. Finally, left = right, so the whole range [first, last) is now examined. From the definitions above, it follows that pt = right.

The following algorithm implements this idea:

template<class It, class T>
It upper_bound(It first, It last, const T& value) {
    auto left  = first;
    auto right = last;

    while (left < right) {
        const auto mid = left + (right - left) / 2;
        if (*mid <= value)        // update left,  i.e. expand [first, left)
            left = mid + 1;
        else                      // update right, i.e. expand [right, last)
            right = mid;
    }

    return right;
}

Note that we're dealing with half-open ranges. We want to include mid into one of the expanded ranges. That's why we set left, the right (excluded) boundary, to mid + 1, but we set right, the left (included) boundary, to mid.

All these can be easily rewritten in terms of indices and is left as a simple exercise.