Results 1 to 13 of 13
 10312010, 03:35 AM #1Member
 Join Date
 Oct 2010
 Posts
 12
 Rep Power
 0
Help with Binary recursive method to find the largest integer
The program like the title says is supposed to return the largest integer value in an userinputted integer array, using binary recursion.
And in the case of an empty array, return Integer.MIN_VALUE.
The program compiles fine, but would always return a "java.lang.StackOverflowError".
I am thinking maybe I got the logic of the code wrong or something.
Below is my code, thanks for helping!!
Java Code:public static void main(String[] args) throws IOException { // TODO Autogenerated method stub int n=0, i; //n will store the user input for the number of integers //it is set to its default value 0 //i will serve the purpose of a counter int[] array; //creating a double array //The line below creates a reference to a new Scanner object // called "sc". It reads lines from standard input one at a time. Scanner sc = new Scanner (System.in); boolean checkException = false;//creates a boolean variable checkException //and sets it to its default value false do { System.out.print ("How many integers would you like to enter? "); try { n = sc.nextInt(); // stores the next integer typed by the user in n using Scanner sc checkException = true;//sets the boolean value to true, will cause //the dowhile loop to exit } catch (InputMismatchException e)//catch values that are not integers { System.out.println("This is not a correct integer, please try again.");//error message sc.next(); //clears Scanner sc for next input checkException = false;//sets boolean value to false, continues the loop } catch(ArrayIndexOutOfBoundsException a)//catches an array that has been accessed with an //illegal index, either negative or greater than or //equal to the size of the array { System.out.println("This is not a correct integer, please try again."); sc.next();//clears Scanner sc for further input checkException = false; } array = new int[n]; //declares the array variable array, giving it n elements } while (checkException == false); //remains in loop as long as the boolean variable is false checkException = false; for (i=0; i<array.length; i++) { do { System.out.println("Please enter your number:"); try { array[i]= sc.nextInt();//stores the user inputs into the indexed array elements checkException = true; } catch (InputMismatchException e)//catches noninteger values and display the error message { System.out.println("This is not a correct integer, please try again."); sc.next(); } } while (checkException == false); } findMaxInt(array); } public static void findMaxInt (int [] array) { findMaxInt(array, 0, array.length1); } public static int findMaxInt (int []array, int start, int end){ if (array.length==0) System.out.println(Integer.MIN_VALUE); if (start>end) return array[start]; int mid= (start+end)/2; if (findMaxInt(array, start, mid)>findMaxInt(array, mid+1, end)) { return findMaxInt(array, start, mid); } else { return findMaxInt(array, mid+1, end); } }
 10312010, 04:13 AM #2
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 21
could you please post the complete error message here to see?
 10312010, 06:07 AM #3Member
 Join Date
 Oct 2010
 Posts
 12
 Rep Power
 0
Java Code:How many integers would you like to enter? 4 Please enter your number: 1 Please enter your number: 2 Please enter your number: 3 Please enter your number: 4 [COLOR="Red"]Exception in thread "main" java.lang.StackOverflowError at BinaryRecursiveFindMax.findMaxInt(BinaryRecursiveFindMax.java:102) at BinaryRecursiveFindMax.findMaxInt(BinaryRecursiveFindMax.java:102) at BinaryRecursiveFindMax.findMaxInt(BinaryRecursiveFindMax.java:102)[/COLOR]
 10312010, 08:28 AM #4
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 21
If you carefully look at the complete start trace then you can find the line of your code that cause this error. Can't you find that?
However it's difficult to track the stack over flow errors easily.
 10312010, 08:35 AM #5
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 21
Revisit this recursive invoke.
Java Code:if (findMaxInt(array, start, mid)>findMaxInt(array, mid+1, end)) { return findMaxInt(array, start, mid); }
Note that, these kind of error may cause lots of issues, not only on your application, may be on other applications which are running at the moment.
 10312010, 08:48 AM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,271
 Blog Entries
 7
 Rep Power
 24
 10312010, 09:01 AM #7
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 21
Let see that op could grab it. ;)
 10312010, 02:51 PM #8Member
 Join Date
 Oct 2010
 Posts
 12
 Rep Power
 0
I changed it up a little bit, and made a call table, and realized that i should have changed "else if (start>end)" to "else if (start>=end)". It seems to work fine now. Thanks for your help!
Java Code:public static int findMaxInt (int []array, int start, int end){ if (array.length==0) System.out.println(Integer.MIN_VALUE); else if (start>=end) return array[start]; else if ((endstart)==1){ if (array[start]>array[end]) { return array[start]; } else return array[end]; } int curmax1, curmax2; int mid= (start+end)/2; curmax1=findMaxInt(array, start, mid); curmax2=findMaxInt(array, mid+1, end); if (curmax1>curmax2) return curmax1; else return curmax2; }
Last edited by flyingcurry; 10312010 at 04:15 PM.
 10312010, 04:14 PM #9Member
 Join Date
 Oct 2010
 Posts
 12
 Rep Power
 0
I just tried inputting 0 as the array length. And it just gave me a stackoverflow.
2147483648
2147483648
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.SingleByteEncoder.encodeArrayLoop(Singl eByteEncoder.java:95)
at sun.nio.cs.SingleByteEncoder.encodeLoop(SingleByte Encoder.java:134)
at java.nio.charset.CharsetEncoder.encode(CharsetEnco der.java:544)
at sun.nio.cs.StreamEncoder$CharsetSE.implWrite(Strea mEncoder.java:384)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java: 136)
at java.io.OutputStreamWriter.write(OutputStreamWrite r.java:191)
at java.io.BufferedWriter.flushBuffer(BufferedWriter. java:111)
I don't know how else to return the "Integer.MIN_VALUE"， it's required in the assignment to return this when an array is empty.
 10312010, 04:43 PM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,271
 Blog Entries
 7
 Rep Power
 24
Oh dear, why all that fiddling with the index? Consider this: let lo be the lowest index in the array to consider and let hi be the index of the rightmost number we don't consider. When we start the algorithm we have lo= 0 and hi= array.length.
The maximum value is either in the range [lo, mid) or in the range [mid, hi) where mid= (lo+hi)/2, i.e. the index of the element near the middle. If lo >= hi there are no elements to consider and if lo == hi1 there's only one element in the array to consider so it is the maximum value of the array in that range.
All this sort of naturally translates to:
Java Code:private static int max(int[] a, int lo, int hi) { if (lo >= hi) return Integer.MIN_VALUE; if (lo == hi1) return a[lo]; int mid= (lo+hi)/2; return Math.max(max(a, lo, mid), max(a, mid, hi)); }
Jos
 10312010, 05:22 PM #11Member
 Join Date
 Oct 2010
 Posts
 12
 Rep Power
 0
Oh wow, yes,a much simpler interpretation. I have some questions though,
1. why does is it if (lo == hi1) return a[lo];? how do we know that array[lo] will be the larger one?
2. Why is it "return Math.max(max(a, lo, mid), max(a, mid, hi));"
and not "return Math.max(max(a, lo, mid), max(a, mid+1, hi));"
 10312010, 05:50 PM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,271
 Blog Entries
 7
 Rep Power
 24
1) if lo == hi1 we only consider one element and the maximum of an array with one element is just that element.
2) We consider all elements starting from lo (inclusive) up to hi (exclusive) so the left part of the array is [lo, mid) and the right part is [mid, hi) (pay attention to the different brackets).
kind regards,
Jos
 10312010, 07:14 PM #13Member
 Join Date
 Oct 2010
 Posts
 12
 Rep Power
 0
Similar Threads

Recursive Binary Search
By EternalSolitude in forum New To JavaReplies: 2Last Post: 11212008, 07:26 AM 
Recursive Method ==> find minimum value from array
By NatNat in forum New To JavaReplies: 1Last Post: 02162008, 10:10 PM 
Recursive Method ==> find how many times a value is repeated in an array
By NatNat in forum New To JavaReplies: 2Last Post: 02162008, 09:52 PM 
Finding largest and smallest integer
By mlhazan in forum New To JavaReplies: 2Last Post: 01122008, 11:30 PM 
problem with recursive binary search program
By imran_khan in forum New To JavaReplies: 3Last Post: 08022007, 03:08 PM
Bookmarks