/***************************************************************
* Name: Prof. Rafael Orta
* Course: Computer Science & Programming
* Class: CS04225
*****************************************************************
* Purpose: Demonstrate Binary search using a recursive function
*****************************************************************/
#include <iostream>
using namespace std;
void search (const int orderedArray[], int first, int sizeA, int target, bool& found, int& location, int& noSearches);
int main()
{
int orderedArray[]={5,15,21,23,30,31,35,36,40,50,55}; // Array to be searched.
int sizeA = 11; // Variable used to keep track of the sub-array size of be searched.
int first = 0; // Variable used to keep track of the middle + 1 in a new search.
int location = 0; // Keeps tract of the location where the element was found.
int target = 0; // Hold the value of the number to be searched.
int noSearches = 0; // Keeps track of the number of searches.
bool found; // Boolean variable that controls if the number was found or not.
cout << "What is the number you would like to find in the array: ";
cin >> target;
search (orderedArray, first, sizeA, target, found, location, noSearches);
if (found){
cout << "We found the element in position: " << location << " and it took: " << noSearches << " comparisons." << endl;
}
else
cout << "That element is not part of the array," << " and it took: " << noSearches << " comparisons." << endl;
return 0;
}
void search (const int orderedArray[], int first, int sizeA, int target, bool& found, int& location, int& noSearches){
int middle; // Variable used to calculate the middle.
noSearches = noSearches + 1;
//cout << "\nThe value of first is: " << first << endl;
if (sizeA == 0) // In case the element is not found in the array.
found = false;
else
{
middle = first + sizeA/2;
cout << "Searching: " << sizeA << " elements using as middle: " << middle << " and the array value in middle is: " << orderedArray[middle] << endl;
if (target == orderedArray[middle]) // Case where you found the target
{
location = middle;
found = true;
}
else if (target < orderedArray[middle]) // Case where target is less than the middle
search(orderedArray,first, sizeA/2, target, found, location, noSearches);
else
search(orderedArray, middle+1, (sizeA-1)/2, target, found, location, noSearches); // Case where the target is more than the middle.
}
}
