Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #82499

binary_search accoring to its name

Show all headers | 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