#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_FIBONACCIAN_SEARCH_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_FIBONACCIAN_SEARCH_BASIC

namespace Searching_algorithms {
	namespace Fibonaccian_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 fib = find_fibonacci_number( c - a );

					int b;

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

					// cout << a << " " << b << " " << c << endl;

					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 );
					}
				}

			private:
				static
				int find_fibonacci_number( int n ) {
					for ( int i = 0; true; ++i ) {
						if ( fibonacci_numbers[i] > n ) {
							return fibonacci_numbers[i - 1];
						}
					}
				}

				static
				int const fibonacci_numbers[46];
		};

		int const Basic::fibonacci_numbers[46] = {
			1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
			610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
			28657, 46368, 75025, 121393, 196418, 317811, 514229,
			832040, 1346269, 2178309, 3524578, 5702887, 9227465,
			14930352, 24157817, 39088169, 63245986, 102334155,
			165580141, 267914296, 433494437, 701408733,
			1134903170, 1836311903, 2147483647
		};
	}
}

#endif