#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_INTERPOLATION_SEARCH_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_INTERPOLATION_SEARCH_BASIC

namespace Searching_algorithms {
	namespace Interpolation_search {
		class Basic {
			public:
				template <typename Type>
				static
				bool search( Type const &obj, Type *array, int n ) {
					if ( obj < array[0] || array[n - 1] < obj ) {
						return false;
					}

					return search_recursive( obj, array, 0, n - 1 );
				}

				template <typename Type>
				static
				bool search( Type const &obj, Type *array, int a, int b ) {
					if ( obj < array[a] || array[b] < obj ) {
						return false;
					}

					return search_recursive( obj, array, a, b );
				}

			private:
				template <typename Type>
				static
				bool search_recursive( Type const &obj, Type *array, int a, int c ) {
					if ( a > c ) {
						return false;
					} else if ( array[a] == array[c] ) {
						return array[a] == obj;
					}

					int b = a + static_cast<int>(
						static_cast<double>( c - a )*
						static_cast<double>( obj - array[a] )/
						static_cast<double>( array[c] - array[a] )
					);

					if ( array[b] == obj ) {
						return true;
					} else if ( obj < array[b] ) {
						if ( b - 1 < a || array[b - 1] < obj ) {
							return false;
						}

						return search_recursive( obj, array, a, b - 1 );
					} else {
						if ( b + 1 > c || array[b + 1] > obj ) {
							return false;
						}

						return search_recursive( obj, array, b + 1, c );
					}
				}
		};
	}
}

#endif