A generic binary search function in C++

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.

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.

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).