I am having a lot of trouble finding the largest number in a binary search using recursion. The book gives me some basic code on how to search on, but not how to find the largest number in one. The question asks me to implement this a helper function but to start, I just want to get the inner workings down.
Say that i had an array of {1,6,8,3} and i had to use recursion to find the largest number in it.
this is the example that was given to search for an value in the array that was already given.
Code:
#include<iostream>
using namespace std;
int binarySearch(const int anArray[], int first, int last, int value)
{
int index;
if (first >last )
index =-1;
else
{ //invariant : If value is in AnArray,
// anArray[first] <= value <= anArray[last]
int mid = (first + last)/2;
if ( value==anArray[mid])
index = mid; //value found at mid;
else if (value <anArray[mid])
// point x
index = binarySearch(anArray, first, mid-1, value);
// keep in mind that mid-1 become the "last" in the next recursive call
else
//point y
index = binarySearch(anArray, mid+1, last, value );
// keep in mind that "mid+1" will be first in the next recursive call
// as in (first+last)/2, the value at mid+1 is now firsts.
} // end if
return index;
}//end binarySearch
int main()
{
int first=0;
int last=7;
int value=29;
int anArray1[]={1,5,9,12,15,21,29,31};
binarySearch(anArray1, first, last, value);
//cout << value << endl ;
system("pause");
return 0;
}
the book gives
this as in what it wants in the example.
if( anArray has only 1 item)
maxArray(anArray) is the item in the array
else if (anArray has more than 1 item)
maxArray(anArray) is the maximum of
maxArray(left half of anArray) and
maxArray(right half of anArray)
any suggestions?