finding the largest number in a binary search

This is a discussion on finding the largest number in a binary search within the C++ Programming forums, part of the General Programming Boards category; I am having a lot of trouble finding the largest number in a binary search using recursion. The book gives ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    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. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    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. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,343
    If I'm understanding your description, the approach assumes the array is sorted.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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)
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  7. #7
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    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. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Emeighty View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    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. #10
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    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. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Quote Originally Posted by Emeighty View Post
    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!
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Dino View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    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. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with binary search.
    By StateofMind in forum C Programming
    Replies: 6
    Last Post: 05-06-2009, 02:14 PM
  2. Issue w/ Guess My Number Program
    By mkylman in forum C++ Programming
    Replies: 5
    Last Post: 08-23-2007, 01:31 AM
  3. Replies: 3
    Last Post: 11-25-2006, 03:14 PM
  4. Replies: 9
    Last Post: 10-07-2006, 05:37 AM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21