#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_BINARY_SEARCH_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_BINARY_SEARCH_ARRAY

#include "Linear_search_array.h"

namespace Searching_algorithms {
	namespace Binary_search {
		int const ARRAY_USE_LINEAR = 18;

		class Array {
			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_iterative( 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_iterative( obj, array, a, b );
				}

			private:
				template <typename Type>
				static
				bool search_iterative( Type const &obj, Type *array, int a, int c ) {
					while ( c - a >= ARRAY_USE_LINEAR ) {
						int b = a + ((c - a) >> 1);

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

					return Searching_algorithms::Linear_search::Array::search( obj, array, a, c );
				}
		};
	}
}

#endif