Skip to content

Instantly share code, notes, and snippets.

@axper
Created May 22, 2014 16:59
Show Gist options
  • Save axper/98d77edeeefee3efe9e9 to your computer and use it in GitHub Desktop.
Save axper/98d77edeeefee3efe9e9 to your computer and use it in GitHub Desktop.
Microsoft C++ homework for May 20
#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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment