A generic binary search function in C++

Question

I have written the following generic function template:

#include <iostream>
#include <array>
#include <span>
#include <iterator>
#include <concepts>
#include <compare>
#include <cstddef>
template <typename T>
requires ( std::totally_ordered<T> && std::three_way_comparable<T> )
[[ nodiscard ]] constexpr std::ptrdiff_t
binarySearch( const std::span<const T> spn, const T target) noexcept
{
 std::ptrdiff_t result;
 std::ptrdiff_t lowerBound { };
 std::ptrdiff_t upperBound { std::distance( std::cbegin( spn ), std::cend( spn ) ) - 1 };
 while ( lowerBound <= upperBound )
 {
 std::ptrdiff_t mid { lowerBound + ( upperBound - lowerBound ) / 2 };
 if ( spn[ mid ] == target )
 {
 return result = mid;
 }
 else if ( spn[ mid ] < target )
 {
 lowerBound = mid + 1;
 }
 else
 {
 upperBound = mid - 1;
 }
 }
 return result = -1;
}
int main( )
{
 const std::array<long long, 5> arr { 3, 44, 44, 1000, 1050 };
 const auto lowerBound { std::cbegin( arr ) };
 const auto upperBound { std::cend( arr ) };
 const long long target { 44 };
 std::ptrdiff_t resultIndex { binarySearch( { lowerBound, upperBound } , target ) };
 if ( resultIndex == -1 )
 {
 std::cout << "The element <<" << target
 << ">> is not present in the span\n";
 }
 else
 {
 std::cout << "The element <<" << target << ">> is present at index "
 << resultIndex << " of the span\n";
 }
}

• Is the above function safe and robust? I want to discover the potential flaws that it has.
• What parts of it could be improved? For instance what other concepts should I add to the requires clause?

Also, I want to mention that I aim to make sure that T is a type that when compared using comparison operators, results in either a std::strong_ordering or a std::weak_ordering so that the binary search algorithm works properly. Is this a good idea? And if so then how should I ensure that it happens?

• hanshenrik: i despise "short/long/long long", "int8/int16/int32/int64" is much better imo, but that's personal preference ofc.
• digito_evo: @hanshenrik I prefer fixed integer types too. Like std::uint64_t. However I chose something else for this example.

Answer 1

Using std::span isn't very general. I'd go for a concept such as ranges::random_access_range auto const& to allow the function to be used with containers having discontiguous storage.

Passing target by value may hurt performance, and need not even be possible if it's a non-copyable type - for a general search, I would make that a reference to const. We might not even want the target to be the same type as the collection (think of string-views, for example) - we just want something that's totally ordered with it.

We require std::three_way_comparable<T> but then use == and < when comparing. Why not use a single <=> opteration, and use the result from that to switch between the three different actions?

result is a local, so there's no point assigning to it as we return. Just return mid or -1, and eliminate the variable.

We need more tests - the single test we have does not exercise the full set of code paths.

• digito_evo: But I remember that I once read in a book that we shouldn't use the spaceship operator when comparing values and only use it when we want to implement the 4 comparison operators for our class. Isn't it right?
• Toby Speight: If we go with that approach, then I don't see why we need to require std::three_way_comparable - it should be sufficient to require just the total ordering. I think we should either require <=> and use it, or not require it and not use it.
• digito_evo: Oh so I didn't need that concept from the beginning? And the code will be fine without it? Nice.

Answer 2

Using appropriate concepts

It's good to be strict with requirements on inputs, but not more strict than necessary. Three way comparison shouldn't be a requirement to do binary search, total ordering is enough. Therefore it would be good to drop the std::three_way_comparable requirement. The implementation wasn't using it anyway!

Finding the insertion index

A common feature of binary search functions in standard libraries is that when the target is not found, then return an -1 -insertAt, where insertAt is the position where the value could be inserted to preserve the correct ordering. It's ok to keep the implementation simple, though I think it wouldn't add much complexity to add support for this common feature.

Either way, it would be good to document the function to explain the returned value when the target is not found.

• digito_evo: Thanks for the suggestions. Now I also have a bad feeling about returning an index (std::ptrdiff_t) and I feel like it's hard to deal with from the client side. Wouldn't it be better and more appropriate to return an iterator (std::span<const T>::iterator)?
• janos: @digito_evo hm, I kind of stand corrected. std::binary_search returns bool. From that doc page you also find std::lower_bound, and other interesting functions, which do return iterators...

Answer 3

Suggestions

We can remove useless result variable.

If possible, shorten if statements to avoid excessive nesting of code blocks.

Make target a lvalue reference const T&.

std::span is merely a contiguous sequence, therefore we should specify whether spn interval is half-open or closed. Following the test case, spn is half-open as usual, but in the algorithm we transform it to the closed interval [lowerBond, upperBound]. For clarity, skip redundant index calculations and leave it half-open.

/*...*/
binarySearch( const std::span<const T> spn, const T& target) noexcept
{
 std::ptrdiff_t lowerBound { };
 std::ptrdiff_t upperBound { std::distance( std::cbegin( spn ), std::cend( spn ) ) };
 while ( lowerBound < upperBound )
 {
 std::ptrdiff_t mid { lowerBound + ( upperBound - lowerBound ) / 2 };
 if ( spn[ mid ] == target ) 
 return mid;
 
 if ( spn[ mid ] < target ) 
 lowerBound = mid + 1; 
 else 
 upperBound = mid; 
 }
 return -1;
}

span may complicate user code

It is because the function returns a relative offset instead of an actual iterator or an absolute offset at least. Probably the approach was chosen deliberately to make the function more generic, but consider the use case.

struct Entry {
 int key = 0;
 int data = 0;
 bool operator<(const Entry& rhs) const noexcept {
 return key < rhs.key;
 }
 friend bool operator==(const Entry& lhs, const Entry& rhs) noexcept {
 return lhs.key == rhs.key;
 }
};
int main() {
 std::vector<Entry> v = {
 {1, 2}, {3, 4}, {5, 6}, {7, 8}
 };
 Entry target{7, 0};
 auto pos = binarySearch({std::begin(v) + 2, std::end(v)}, target);
 if (pos != -1) {
 auto it = std::begin(v) + 2 + pos;
 std::cout << it->data << '\n';
 }
 
 // compare to
 auto it = std::lower_bound(std::begin(v) + 2, std::end(v), target);
 if (it != std::end(v))
 std::cout << it->data << '\n';
 
 return 0;
}

Normally, we would set a left bound auto start = std::begin(v) + 2;. But still, we have to deal with intermediate integers.

As an alternative, we could write a constexpr function without span.

Add a binary predicate to compare values

To make the function more generic, replace value comparison with predicate evaluation.

template <typename T, typename Compare>
/* ... */
binarySearch( const std::span<const T> spn, const T target, Compare comp) noexcept {
 /* ... */
 if (comp(spn[ mid ], target))
 /* ... */
}

begin vs cbegin

It looks like we can be less specific and replace std::cbegin with std::begin.

Less restrictions -> more generic

As a rule of thumb, we should require only necessary type traits.

I would suggest adding such predicate Compare that establishes the std::strict_weak_order relation. For example,

#include <iostream>
#include <functional>
struct Entry {
 int key = 0;
 int data = 0;
 bool operator<(const Entry& rhs) const noexcept {
 return key < rhs.key;
 }
 friend bool operator==(const Entry& lhs, const Entry& rhs) noexcept {
 return lhs.key == rhs.key;
 } 
};
template<typename In,
 typename T,
 typename Compare = std::less<T>>
requires(std::strict_weak_order<Compare, T, T>)
auto mySearch(In b, In e, const T& x, Compare comp = {})
{
 return std::lower_bound(b, e, x, comp);
}
int main()
{
 std::vector<Entry> v = {
 {1, 2}, {3, 4}, {5, 6}, {7, 8}
 }; 
 auto it = mySearch(begin(v), end(v), Entry{7, 0});
 std::cout << it->data;
 return 0;
}

Equality condition may be rewritten like !comp(lhs, rhs) && !comp(rhs, lhs).