Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
math::binsearch Namespace Reference

Classes

class  Function
class  ConvexFunction
class  FunctionBinsearch

Functions

template<typename T >
range_middle (T left, T right)
template<typename ValueType , typename SizeType >
SizeType lower_bound (ValueType pole[], SizeType left, SizeType right, ValueType value)
template<typename ValueType , typename SizeType >
SizeType upper_bound (ValueType pole[], SizeType left, SizeType right, ValueType value)

Function Documentation

template<typename ValueType , typename SizeType >
SizeType math::binsearch::lower_bound ( ValueType  pole[],
SizeType  left,
SizeType  right,
ValueType  value 
)

Find first index in array range [left, right) where the value may be inserted without violating the ordering

Note that the definition is same as ``index of first element which is >= value'' except that the result is right if no such value exists

Example:

     a = 1 1 2 2 2 3 5
 lb(1) = ^
 lb(2) =     ^
 lb(4) =             ^
 lb(6) =               ^ (==right)
 
Precondition:
  • sorted array
  • SizeType is integral type
  • (right-left) will fit into type SizeType
Parameters:
leftstart of the interval
rightindex after the end of the interval
Returns:
index of the binsearched value
template<typename T >
T math::binsearch::range_middle ( left,
right 
)

Finds the middle of the range [left, right)

Middle is defined as floor((left + right) / 2)

Precondition:
  • T is integral type
  • (right-left) is representable in type T
Parameters:
leftstart of the interval
rightfirst index after the end of the interval
Returns:
midde of the interval
template<typename ValueType , typename SizeType >
SizeType math::binsearch::upper_bound ( ValueType  pole[],
SizeType  left,
SizeType  right,
ValueType  value 
)

Finds last position from range [left, right) where the value may be inserted without violating ordering

Note that the definitions is the same as ``index of first element that is greater than value'' except that the result is right if no such value exists

Example:

       1 1 2 2 3 5
 ub(6)             ^ (== right)
 ub(2)         ^
 ub(1)     ^
 ub(0) ^
 
Precondition:
  • (right-left) should fit into ValueType
  • SizeType should be integral type
Parameters:
leftstart of the interval
rightindex after the end of the interval
Returns:
index of the binsearched value
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines