3
\$\begingroup\$

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;

}
\$\endgroup\$

3 Answers 3

4
\$\begingroup\$

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;
}
\$\endgroup\$
11
  • \$\begingroup\$ This still suffers from 2log(N) comparisons instead of log(N)+1 many. I know of interviewers who reject this solution. \$\endgroup\$
    – Maikel
    Apr 18, 2017 at 18:39
  • \$\begingroup\$ @Maikel: Well that just goes to show there are bad interviewers out there. If they reject a perfectly good candidates their loss because I'll hire somebody with this solution. The thing to note in an interview is The other things is if you have multiple values that match your key then you return a random one of these values. I agree that it could be optimized. But I prefer to go with readability first then optimize if required later. \$\endgroup\$ Apr 19, 2017 at 4:20
  • \$\begingroup\$ @Maikel: O(log(n)) is the same as O(2.log(n)) in complexity. \$\endgroup\$ Apr 19, 2017 at 4:27
  • \$\begingroup\$ Thats why omitted big-O notation and talk about its constants. I just think that algorithmic deficits are more important tham stylistic ones. \$\endgroup\$
    – Maikel
    Apr 19, 2017 at 4:39
  • \$\begingroup\$ Your solution also does not return a random equivalent element. That would require looking for lower and upper bounds of equivalent elements and a rng. Its all not too important anyway. I just wanted to note that the solution lacks something algorithmically. \$\endgroup\$
    – Maikel
    Apr 19, 2017 at 4:59
7
\$\begingroup\$
  • 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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Using const on input parameters (i.e. on key), which are given by value is at least debatable. \$\endgroup\$
    – Maikel
    Apr 18, 2017 at 9:35
  • \$\begingroup\$ @Maikel I just don't think changing key to be searched from within search function shoud be allowed, so why not make compiler enforce this. \$\endgroup\$
    – Nykakin
    Apr 18, 2017 at 9:44
  • \$\begingroup\$ In general, if I define an interface all I care is that key is not getting modified on the outside, but I do not care what the actual implementation does with it. \$\endgroup\$
    – Maikel
    Apr 18, 2017 at 10:11
2
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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