C++ Binary Search

Question

Could you advise on this binary search implementation?

template<typename Iterator, typename T>
Iterator binarySearch(Iterator begin, Iterator end, const T& v) {
    Iterator low = begin;
    Iterator high = end - 1;
    while (low <= high)
    {
        Iterator mid = low + (high - low) / 2;
        if (*mid == v) {
            return mid;
        }
        else if (*mid < v) {
            low = mid + 1;
        } else {
            if (mid == begin) { 
                return end;
            }
            high = mid-1;
        }
    }
    return end;
}

The mid==begin line is unfortunate but cannot think of a more elegant approach here, welcoming ideas.

Answer 1

Your implementation follows a c bsearch interface, and has the same problems.

First, if a target is not found, the entire work is thrown away. You essentially return one bit of information. Second, if there are duplicates, you return an arbitrary one.

c++ solves these problems with the std::lower_bound, which always returns a meaningful iterator - a partition point. All elements to the left are less than target, all the rest are greater or equal.

---

The mid == begin is indeed unfortunate, and stems from high being inside the search range. If you initialize it as high = end, and modify it as high = mid instead, high would always be beyond the current search range. Of course, a loop condition should be low < high. If it happens that low == high, the search range is exhausted, and the loop naturally breaks.

Notice that working with semi-open ranges is much simpler, and c++ algorithms always follow this pattern.

---

You assume a random access iterator. The standard search algorithms only require forward iterators.

Answer 2

There are several possible improvements to your approach.

First, you can omit the second template parameter by making use of decltype(*std::declval<Iterator>()) What does this mean? So, the std::declval<Iterator>() fakes the construction of an Object of type Iterator. The star before it derefences this iterator, which in turn gives us the stored value and the decltype gives us the respective type to this stored value.

Second, you can avoid most of the comparisons changing how your search works. Instead, as already proposed by others, you can write a lower_bound-Function, that gives you the iterator next to val, that is, v<=*it and for every iterator right from it we have v<*it and changing the meaning of the parameter end: this iterator should not be part of the range, resulting in a left-closed-right-open implementation.

Put together a possible implementation could look like the following. I did not test it, but the idea should be clear in case of any misspellings:

template<typename Iterator>
Iterator binarySearch(Iterator begin, Iterator end, const  std::decay_t<decltype(*std::declval<Iterator>())>& v {
        auto diff = end - begin;
        while (diff > 1)
        {
           auto mid = low + diff / 2;
           if (v < *mid)
               end = mid;
           else // v >= *mid
               begin = mid;
           diff = end - begin;
        }
        if (begin == end || *begin < v)
           return end;
        return begin;
}

One could further improve this by making use of right-shift operations, and omitting the setting of the end-iterator in the loop.

Answer 3

The principle of binary search

The fundamental principle of binary search is this: discard half of the input on every iteration in order to make exponential progress.

Let's look at a related algorithm that uses the same principle. It is called lower_bound in C++'s STL. It could also more descriptively be called binary_search_leftmost_not_less_than. Here's a simple implementation:

// searches the sorted range `[begin, end)` for the
// leftmost value that is not less than `needle`
 1. while (begin != end) {
 2.   assert(begin < end);
 3.   auto p = begin + (end - begin) / 2;

 4.   if (*p < needle) {
 5.     begin = p + 1;
 6.   } else {
 7.     end = p;
 8.   }
 9. }

10. return begin;

I love this algorithm for the following reasons:

• it is extremely concise;
• it is efficient;
• every line illustrates an important binary search mechanic.

Here's a short breakdown of the implementation:

There are only two comparisons per iteration at lines 1 and 4 (assuming the defensive assert at line 2 is optimized away or removed)`

Line 3 is the classic midpoint computation.

It stays true to the aforementioned principle: make exponential progress at every iteration. It either discards the first half of the input at line 5 or it discards the second half of the input at line 7.

Note that p never "remains" on the search range after each iteration, so there's no possibility of infinite loop. Progress is always made since at least one element is guaranteed to be discarded:

• line 5 explicitly removes p by moving begin immediately after it;
• line 7 makes it the end iterator, which can be somewhat confusing. But remember that the search range is closed on begin but open on end, so p remains right there on the edge but is not quite part of the search range.

The search range is progressively narrowed down until it is exhausted, at which point begin and end will point to the same element. That element will either be the original end, or it will be the leftmost element not-less-than needle (that is, greater or equal). That iterator is returned at line 10.

Keep it simple

As stated before, lower_bound is guaranteed to return either the input's original end iterator in case of a failed search, or an element that is greater than or equal to needle in case of success.

With a couple extra conditionals, binary search can be implemented in terms of lower_bound, as follows:

// searches for `needle` in the sorted range `[begin, end)`
1. auto i = lower_bound(begin, end, needle);

2. return i != end && *i == needle
3.   ? i
4.   : end;

The extra conditionals are in line 2. The first one checks whether lower_bound succeeded or not. The second one checks whether a successful search yielded an element that is equal to needle or greater than it.

Line 3 is evaluated on successful searches that found an element that's equal to needle, representing a successful binary search.

Line 4 is evaluated otherwise (failed or greater than), representing a failed binary search.

One might argue that two extra conditionals are too many conditionals, therefore it is better to move the equality check into the loop and bail out early in case of success.

This brings me to a seemingly unimportant observation about the code presented in the original question, which performs this equality check inside the loop. Assuming random input:

The exact match check optimizes for the less likely case

The very first if statement inside the question's code represents the exact match check. This check will always be evaluated on every loop iteration.

On average, binary search runs lg(n) loop iterations (base 2 logarithm), so the check will be evaluated, on average, lg(n) times, even though it will branch, on average, only 1 out of lg(n) times.

The exact match can branch, by design, at most once since it signifies a successful search and, therefore, the end of the algorithm.

Moving it out of the loop optimizes for the most likely case: that elements will differ from needle and the search range will need to be narrowed down.

That is exactly what the extra conditionals after lower_bound do: they hoist the equality check outside the loop. They are evaluated at most once (i != end is evaluated exactly once, *i == needle is evaluated at most once).

The inlined version

Here's what it would look like if we inline lower_bound in the binary_search implementation:

// searches for `needle` in the sorted range `[begin, end)`
 1. auto const input_end = end;

 2. while (begin != end) {
 3.   assert(begin < end);
 4.   auto p = begin + (end - begin) / 2;
 5.   if (*p < needle) {
 6.     begin = p + 1;
 7.   } else {
 8.     end = p;
 9.   }
10. }

11. return begin != input_end && *begin == needle
12.   ? begin
13.   : input_end;

This is pretty much lower_bound, with a modified return statement.

In my opinion, easy to write, easy to remember, easy to derive from first principles and plenty efficient.

Exact match checking in the else

One might argue that this implementation can be modified to efficiently perform the exact match check inside the loop as follows:

// searches for `needle` in the sorted range `[begin, end)`
 1. auto const input_end = end;

 2. while (begin != end) {
 3.   assert(begin < end);
 4.   auto p = begin + (end - begin) / 2;
 5.   if (*p < needle) {
 6.     begin = p + 1;
 7.   } else if (*p > needle) {
 8.     end = p;
 9.   } else {
10.     return p;
11.   }
12. }

13. return begin != input_end && *begin == needle
14.   ? begin
15.   : input_end;

The else in line 9 is equivalent to the exact match check.

This version is indeed better, on the average case, than the one that performs the exact match check as the first thing in the loop's body.

But now instead of having two conditionals in the loop, we have three at lines 1, 5 and 7.

Conclusion

Note that every single variation explored here can be valid and efficient. It all depends on what the input will look like.

If your input is highly likely to yield an exact match, then by all means move the exact match check inside the loop.

At the end of the day, the best path forward is to measure and analyze, and only then make a judgement call.

The discussion presented here should not be seen as "never do that, do this instead" but rather as a repertoire of techniques that could be employed, with accompanying notes of when they make sense and when they don't.

Unless and until your input is well known, or observed to have properties that can be exploited for efficiency by special casing algorithms, the simple implementation of binary search presented here will do just fine and will likely be optimal.