#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_JUMP_3_SEARCH_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_JUMP_3_SEARCH_ARRAY

#include <cmath>
#include "Jump_search_array.h"

namespace Searching_algorithms {
	namespace Jump_3_search {
		class Array {
			public:
				template <typename Type>
				static
				bool search( Type const &obj, Type *const array, int const n ) {
					return search( obj, array, 0, n - 1 );
				}

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

					int jump = static_cast<int>( std::exp( 2.0*std::log( b - a )/3.0 ) );

					int i = a + jump;

					for ( ; i < b && array[i] < obj; i += jump ) {
						// do nothing
					}

					if ( i > b ) {
						return Searching_algorithms::Jump_search::Array::search( obj, array, i - jump, b );
					} else {
						return Searching_algorithms::Jump_search::Array::search( obj, array, i - jump, i );
					}
				}
		};
	}
}

#endif