Microsoft C++ homework for May 20

recursive_binary_search.cpp

#include <iostream>
using namespace std;


/*
 * This function recursively searches for number lookup in a sorted array
 * which has no repeating values.
 *
 * Parameters:
 *     array: The sorted array to search in
 *     begin: Initial values must be 0
 *     end: Initial value must be array size
 *     lookup: The number to look for in array
 *
 * Returns: The index of matching item, or -1 if not found
 */
int RecursiveBinarySearch(const int array[],
                          const int begin,
                          const int end,
                          const int lookup)
{
	if (begin == end || begin == end - 1) {
		if (lookup == array[begin]) {
			return begin;
		} else if (lookup == array[end]) {
			return end;
		} else {
			return -1;
		}
	} else {
		const int middle = (begin + end) / 2;

		if (lookup == array[middle]) {
			return middle;
		} else if (lookup < array[middle]) {
			return RecursiveBinarySearch(array, begin, middle - 1, lookup);
		} else {
			return RecursiveBinarySearch(array, middle + 1, end, lookup);
		}
	}
}

int main()
{
	const int array[] = { 3, 4, 12, 13, 14, 15, 17, 19, 20, 29, 39, 40, 43 };
	const int size = sizeof(array) / sizeof(array[0]);

	int lookup;
	cout << "Number to look for: ";
	cin >> lookup;

	int result = RecursiveBinarySearch(array, 0, size, lookup);

	if (result == -1) {
		cout << "Not found" << endl;
	} else {
		cout << "Found at index " << result << endl;
	}
}