BinarySearch

Files CCore/inc/algon/BinarySearch.h CCore/src/algon/BinarySearch.cpp

BinarySearchAlgo is an Algorithm Package. It is parametrized by a generalized range type and contains binary search algorithms. The second template parameter is defaulted to the BaseRangeAlgo<R>.

template <class R,class Algo=Algon::BaseRangeAlgo<R> >
struct Algon::BinarySearchAlgo : Algo
 {
  template <class Pred>
  static R Find(R &r,Pred pred); // pred(R) is 0,0,0,...,0,1,1,...
  
  template <class S>
  static R Find_less(R &r,const S &med); // R is decreasing
  
  template <class S>
  static R Find_less_or_equal(R &r,const S &med); // R is decreasing
  
  template <class S>
  static R Find_greater(R &r,const S &med); // R is increasing
  
  template <class S>
  static R Find_greater_or_equal(R &r,const S &med); // R is increasing
 };

Find() is a general binary search algorithm. It's input is a range and a predicate. The range must be increasing relative the predicate, i.e. if some element makes the predicate true, then the further elements do the same. The algorithm splits the range on two parts: prefix consists of elements with the predicate value false, and suffix makes the predicate true. The prefix is returned and the suffix is set back to the r. The first element of suffix, if any, is the first element of the range satisfying the predicate.

Find_less() is a special variant for the predicate "less than med". The range is assumed decreasing.

Find_less_or_equal() is a special variant for the predicate "less or equal than med". The range is assumed decreasing.

Find_greater() is a special variant for the predicate "greater than med". The range is assumed increasing.

Find_greater_or_equal() is a special variant for the predicate "greater or equal than med". The range is assumed increasing.

There is a family of functions for the binary search.

template <class R,class Pred>
R Algon::BinarySearch_if(R &r,Pred pred) { return Algon::BinarySearchAlgo<R>::Find(r,pred); }

template <class R,class S>
R Algon::BinarySearch_less(R &r,const S &med) { return Algon::BinarySearchAlgo<R>::Find_less(r,med); }

template <class R,class S>
R Algon::BinarySearch_less_or_equal(R &r,const S &med) { return Algon::BinarySearchAlgo<R>::Find_less_or_equal(r,med); }

template <class R,class S>
R Algon::BinarySearch_greater(R &r,const S &med) { return Algon::BinarySearchAlgo<R>::Find_greater(r,med); }

template <class R,class S>
R Algon::BinarySearch_greater_or_equal(R &r,const S &med) { return Algon::BinarySearchAlgo<R>::Find_greater_or_equal(r,med); }

They call the correspondent search algorithms from the BinarySearchAlgo.