#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_JUMP_SEARCH_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_JUMP_SEARCH_BASIC

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

namespace Searching_algorithms {
	namespace Jump_search {
		class Basic {
			public:
				template <typename Type>
				static
				bool search( Type const &obj, Type *const array, int const n ) {
					int jump = static_cast<int>( std::sqrt( n ) );

					int i = 0;

					for ( ; i < n && array[i] <= obj; i += jump ) {
						if ( array[i] == obj ) {
							return true;
						}
					}

					if ( i == 0 ) {
						return false;
					} else if ( i >= n ) {
						return Searching_algorithms::Linear_search::Basic::search( obj, &array[i - jump], n - i + jump );
					} else {
						return Searching_algorithms::Linear_search::Basic::search( obj, &array[i - jump], jump );
					}
				}
		};
	}
}

#endif