Results 1 to 13 of 13
  1. #1
    flyingcurry is offline Member
    Join Date
    Oct 2010
    Posts
    12
    Rep Power
    0

    Question 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 user-inputted 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 Auto-generated 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 do-while 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 non-integer 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.length-1);
    
    		}
    
    	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);
    		}
    
    	}

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

  3. #3
    flyingcurry is offline Member
    Join Date
    Oct 2010
    Posts
    12
    Rep Power
    0

    Default

    Quote Originally Posted by Eranga View Post
    could you please post the complete error message here to see?
    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]
    and so on

  4. #4
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

    Default

    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.

  5. #5
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

    Default

    Revisit this recursive invoke.

    Java Code:
    if (findMaxInt(array, start, mid)>findMaxInt(array, mid+1, end))
    		{
    			return findMaxInt(array, start, mid);
    		}
    take a piece of paper and write the logic here. Start with the simple step, take two numbers and think what happen here. You comes with the endless condition here and end up with the stack overflow.

    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.

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,023
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by flyingcurry View Post
    Java Code:
    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);
    		}
    
    	}
    The length of the array never changes no matter what you do with the values of start and/or end; if it wasn't zero it won't become zero and you'll recurse all the way down until the stack overflows.

    kind regards,

    Jos

  7. #7
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

  8. #8
    flyingcurry is offline Member
    Join Date
    Oct 2010
    Posts
    12
    Rep Power
    0

    Default

    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 ((end-start)==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; 10-31-2010 at 03:15 PM.

  9. #9
    flyingcurry is offline Member
    Join Date
    Oct 2010
    Posts
    12
    Rep Power
    0

    Default

    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.

  10. #10
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,023
    Blog Entries
    7
    Rep Power
    20

    Default

    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 == hi-1 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 == hi-1) return a[lo];
    	int mid= (lo+hi)/2;
    	return Math.max(max(a, lo, mid), max(a, mid, hi));
    }
    kind regards,

    Jos

  11. #11
    flyingcurry is offline Member
    Join Date
    Oct 2010
    Posts
    12
    Rep Power
    0

    Default

    Oh wow, yes,a much simpler interpretation. I have some questions though,
    1. why does is it if (lo == hi-1) 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));"

  12. #12
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,023
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by flyingcurry View Post
    Oh wow, yes,a much simpler interpretation. I have some questions though,
    1. why does is it if (lo == hi-1) 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));"
    1) if lo == hi-1 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

  13. #13
    flyingcurry is offline Member
    Join Date
    Oct 2010
    Posts
    12
    Rep Power
    0

Similar Threads

  1. Recursive Binary Search
    By EternalSolitude in forum New To Java
    Replies: 2
    Last Post: 11-21-2008, 06:26 AM
  2. Replies: 1
    Last Post: 02-16-2008, 09:10 PM
  3. Replies: 2
    Last Post: 02-16-2008, 08:52 PM
  4. Finding largest and smallest integer
    By mlhazan in forum New To Java
    Replies: 2
    Last Post: 01-12-2008, 10:30 PM
  5. problem with recursive binary search program
    By imran_khan in forum New To Java
    Replies: 3
    Last Post: 08-02-2007, 03:08 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •