# Thread: finding the largest number in a binary search

1. ## finding the largest number in a binary search

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?

2. So what exactly are you asking for?

Your pseudocode appears to do the right thing, just like the binary search, you'd do "half the range" at a time, until you are at the place where you have only one element. Obviously, you'd need to take the maximum of the two parts to find the value to return.

--
Mats

3. writing code to find the max is the problem. I dont see how i can get the max if the value is not searched in there like the book example gave. I see how to search a value in the array not how to get the largest number in it

4. If I'm understanding your description, the approach assumes the array is sorted.

5. You can only find the max value by searching each element in the array [assuming it's not sorted]. Now imagine you have a stack of "cards" (pieces of cardboard, perhaps) with numbers on them, you have 1000 of them. They all have a different number on them.

One way to find the highest number of those thousand cards would be to search from the card at the top of the pile and "keep" hold of the largest you have found so far.

Another way, particularly if you had lots of people around you, would be to split the pile into smaller piles. If you had 1000 people, you give them a card each. Ask each one of them to compare the card with their neighbour to the left. The person with the lower card steps away. Repeat the process until you only have one person left (it takes 10 steps of "remove the lower" to achieve this). Essentially, your recursive search for the max uses this method: Split the array [pile of cards] into halves, then half that pile until you are down to a single item (array with one element).

--
Mats

6. Why not just start at the root node and go right node, right node, right node, etc., until there are no more right nodes, which would be synonymous with being at the largest value. (Assuming its a sorted binary tree)

7. the array that i need to find the max of is (1,6,8,3}
do i need to learn to sort it. The book doesnt say that i need to sort it.

8. Originally Posted by Emeighty
the array that i need to find the max of is (1,6,8,3}
do i need to learn to sort it. The book doesnt say that i need to sort it.
Correct, you just need to get to a level where you have one element in the array section you are looking at. So your maxarray function should, like the binary search, take a "low, high" range, and if those are equal, you know that you have the max value. So return that.

Otherwise, your maxarray value is the highest of the returned from your left side (low to mid) and the returned from the right side (mid to high).

--
Mats

9. something like this would divide it in half

Code:
```

int mid=(first+last)/2

index=binarysearch(anArray[mid],first, mid-1)```
i have a vision of the goal but getting there is the prob.

writing a code to say
if (binarySearch(anArray[mid], first, mid-1) > (binarySearch(anArray[mid],mid+1)
return binarySearch(anArray[mid],first,mid-1)

how would you pass the half to another function?

10. just a few random questions.
do any of u spend days on one problem with homework and still get nowhere?

did you learn online or in a classroom? I am learning online and it just seems as tho , they dont take baby steps to get the foundation right, sort of just throw u into the fire and grasp a thin rope to try to get out. I bought 3 books to try to get an understanding of topics the crappy textbook doesnt give examples of "How to" It's problably just me, but a simple "this is how you do this ,and here is 5 example of how its done" then things would be much simpler.

Sorry, just had to vent some frustration.

11. I don't have homework (except sometimes on this forum, I try to solve someone elses homework), but certainly some problems can take days to write 5 lines of useful code [1]
, other days, I'd come up with hundreds of lines in one day. And yes, it can be frustrating

It's not the typing bit that is (should be?) hard when it comes to programming. It's about getting your head around the problem.

[1] Or sometimes, you spend a week figuring out that you need to REMOVE two lines of code - now that's productive - particulaly if you have a management that counts lines of code as productivity - fortunately, ours don't.

--
Mats

12. Originally Posted by Emeighty
just a few random questions.
do any of u spend days on one problem with homework and still get nowhere?

did you learn online or in a classroom? I am learning online and it just seems as tho , they dont take baby steps to get the foundation right, sort of just throw u into the fire and grasp a thin rope to try to get out. I bought 3 books to try to get an understanding of topics the crappy textbook doesnt give examples of "How to" It's problably just me, but a simple "this is how you do this ,and here is 5 example of how its done" then things would be much simpler.

Sorry, just had to vent some frustration.
When you do this for a living, you might spend 18 months on one "piece of homework". And it gets even more fun than that, because you are working with several other people, and now you get to use interpersonal skills and be sensitive to other's feelings and all that other crap.

I didn't learn in a classroom or online. I learnt by doing.

So, therefore, enjoy your time in school!

13. Originally Posted by Dino
When you do this for a living, you might spend 18 months on one "piece of homework". And it gets even more fun than that, because you are working with several other people, and now you get to use interpersonal skills and be sensitive to other's feelings and all that other crap.

I didn't learn in a classroom or online. I learnt by doing.

So, therefore, enjoy your time in school!
How true. Commenting that "your code is crap" is not exactly how you win friends and influence people - even if that's what you want to say.

[And I'm an "self-taught" programmer too].

--
Mats

14. To reiterate what matsp said:

You can't do a binary search unless the array is sorted. If the array is sorted (assuming in ascending order) the max value is the last value in the array.

If the array is not sorted, then you will have to compare each element with the next, saving the highest value until you reach the end. Splitting the piles will be faster on a multi-core/multi-processor system but slightly less efficient because of threading overhead. Every element still will have to be compared.

On a related note, the system matsp describes of given each friend 1 card and merging up is a variant of the merge sort called the bottom-up mergesort which is accomplished iteratively as opposed to recursively as is typically of the mergesort.

15. Well, if the list is sorted, we don't need to do anything but know how many there are to find the maximum. The recursive method of searching for the maximum is definite possible. I'm not going to spoil Emeighty's learning by posting code that does it, but it is as described in the original first post: recursively find the max of (left, right) of an array, where the end condition is that one element is (of course) max in itself.

--
Mats