binary_search accoring to its name

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> (permalink)
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

Show key headers only | View raw

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.

Back to comp.lang.c++ | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-27 15:38 +0100
  Re: binary_search accoring to its name Marcel Mueller <news.5.maazl@spamgourmet.org> - 2021-11-28 12:27 +0100
    Re: binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-28 17:03 +0100
    Re: binary_search accoring to its name Juha Nieminen <nospam@thanks.invalid> - 2021-11-29 05:57 +0000
      Re: binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-29 08:26 +0100
        Re: binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-29 14:02 +0100

csiph-web