#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_QUARTER_SEARCH_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_QUARTER_SEARCH_BASIC

// Algorithm designer:  Douglas Wilhelm Harder

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

				template <typename Type>
				static
				bool search( Type obj, Type *array, int a, int c ) {
					if ( c < a ) {
						return false;
					}

					int b;

					if ( obj - array[a] > array[c] - obj ) {
						b = c - (c - a)/4;
					} else {
						b = a + (c - a)/4;
					}

					if ( array[b] == obj ) {
						return true;
					} else if ( obj < array[b] ) {
						return search( obj, array, a, b - 1 );
					} else {
						return search( obj, array, b + 1, c );
					}
				}
		};
	}
}

#endif