Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Bonita Montero <Bonita.Montero@gmail.com>
Newsgroups: comp.lang.c++
Subject: binary_search accoring to its name
Date: Sat, 27 Nov 2021 15:38:54 +0100
Organization: A noiseless patient Spider
Lines: 44
Message-ID: <sntftt$o7$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 27 Nov 2021 14:38:53 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="f7ed9e76340d1946bf18329692dbc5ec"; logging-data="775"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18tQv+NECcFlfFP5KJLegbabb/g4v+o7Es="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.3.2
Cancel-Lock: sha1:bUnwMf9+g/iaAun/RbDQb7UuvAU=
Content-Language: de-DE
Xref: csiph.com comp.lang.c++:82499

This is a somewhat more efficient binary_search, but it requires
that all key in the array are unique. It's more efficient because
it doesn't need two predicate compares to test for equality since
it uses a predicate which returns a stong_ordering-object.
If you're debugging it tests whether the object left and right
from the result are less or greater to ensure uniqueness of the
key-value.

template<typename RandomIt, typename T, typename Pred>
inline
RandomIt xbinary_search( RandomIt begin, RandomIt end, T const &key, 
Pred pred )
	requires std::random_access_iterator<RandomIt>
	&&
	requires( Pred pred, typename 
std::iterator_traits<RandomIt>::value_type &elem, T const &key )
	{
		{ pred( elem, key ) } -> std::convertible_to<std::strong_ordering>;
	}
{
	using namespace std;
	size_t lower = 0, upper = end - begin, mid;
	strong_ordering so;
	while( lower != upper )
	{
		mid = (lower + upper) / 2;
		so = pred( begin[mid], key );
		if( so == 0 )
		{
			assert(!mid || pred( begin[mid - 1], key ) < 0);
			assert(begin + mid + 1 == end || pred( begin[mid + 1], key ) > 0);
			return begin + mid;
		}
		if( so > 0 )
			upper = mid;
		else
			lower = mid + 1;
	}
	return end;
}

Another advantage is, that the supplied key can have a differnt type
than the elements in the array; so you can f.e. check for an member
of an element.