Simple binary search in a vector

Question

I was reading binary search from an interview book and changed some part of the algorithms.

It is working for all the values I tested with: i.e. all the values in array and outside the array extremes. I would appreciate another person's glance on my use of lower <= upper condition. Any other opinion is welcome, too.

std::pair<bool,size_t> BinarySearch(const std::vector<int>& array, int key) {

auto lower = array.begin();
auto upper = array.end()-1;
while (lower <= upper) {
    auto mid = lower + (upper-lower) /2;
    if(key == *mid)
    {
        return {true,std::distance(array.begin(),mid)};
    }
    if(key < *mid)
        upper = mid-1;
    else
        lower = mid+1;
}

return {false,std::distance(array.begin(),lower)};
}

Usage is as follows:

int main(int argc, const char * argv[]) {

std::vector<int> arr {2,5,11,15};
auto result = BinarySearch(arr,5);
if(result.first)
    std::cout << result.second << std::endl;
else
    std::cout << "Not found " << std::endl;
return 0;

}

Answer 1

The main thing I would change is the input type. If you look at the standard library you will find that containers and algorithms are connected via iterators. Thus allowing algorithms to be written for any container type that supports the appropriate iterators.

In your case; why only std::vector? This same algorithm should work for std::array and now you mention it C-Arrays. Which brings us to the return type. If you look at most finding type algorithms they will return an iterator to the element they found; if nothing is found then they return an element to end().

There is no harm adding a wrapper that takes a container then calls the underlying code with std::begin() and std::end().

So first I would change your function to be just a wrapper.

std::vector<int>::const_iterator BinarySearch(const std::vector<int>& array, int key)
{
    return BinarySearch(std::begin(array), std::end(array), key);
}

While we are talking about iterators and generalizing the code.The wrapper can be generalized to any container type (because nothing in the function is dependent on it being a std::vector) by simply adding a template.

template<tyepname C>
auto BinarySearch(C const& cont, int key)
{
    return BinarySearch(std::begin(cont), std::end(cont), key);
}

Range is from beginning to one past end generally.

auto lower = array.begin();
auto upper = array.end()-1;

You have taken the stance that your ranges are inclusive of end. As you will notice this actually makes your code harder when you have empty ranges. But also it makes your split inaccurate.

auto mid = lower + (upper-lower) /2;

To be correct that should have been:

auto mid = lower + ((upper-lower) + 1) /2;

I believe you will find that you slightly pesimizing searches for big numbers but slightly optimizing searches for small numbers.

The other things is if you have multiple values that match your key then you return a random one of these values. It might be more logical to return the first one? If you want to return a random one then you should definitely document that fact.

template<typename I>
I BinarySearch(I begin, I end)
{
    I lower = begin;
    I upper = end;
    while (lower < upper)
    {
        I mid = lower + std::distance(upper, lower) / 2;
        if(key == *mid)
        {
            return mid;
        }
        if(key < *mid) {
            upper = mid;
        }
        else {
            lower = mid;
        }
    }

    return end;
}

Answer 2

• Your code fails if you pass an empty vector because in this case array.end()-1 is incorrect
• Keep const correctness, key should be const too
• You have kind of strange code formatting, you should rather create an indent after every opening bracket, and not keep function body on a same level
• Consider imitating STL approach and returning iterator instead of std::pair
• You limit yourself to std::vector<int> type. Read about templates and try to make code that accept different types as well, for example std::vector<double>.
• Calling std::vector an array is confusing, note that there's also std::array in C++11 and C-style arrays. vec would be better name there.
• Size of std::vector<int> is not actually std::size_t but std::vector<int>::size_type

Answer 3

In addition to @Nykalin I want to add an algorithmic nitpick.

Your equality test

if(key == *mid)

is an additional comparison in each step. Imagine your are not looking for ints but in a vector of large std::strings. Just make an upper_bound-like search and test this bound. Schematically:

template <typename I, typename T>
I binary_search(I first, I last, const T& value)
{
  I ub = upper_bound(first, last, value);
  assert(!(*ub < value));
  // Equality means: !(*ub < value) && !(value < *ub)
  if (ub != last && !(value < *ub)) {
    return ub;
  }
  return last;
}

You will see that implementing upper_bound is very simple and beautiful in comparison to a direct binary_search.

Edit:

What I call here "upper_bound"-like search is implemented in the STL as std::lower_bound not to confuse with std::upper_bound.