Help with Binary recursive method to find the largest integer

[flyingcurry]

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!!

	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);
		}

	}

[Eranga]

could you please post the complete error message here to see?

[flyingcurry]

could you please post the complete error message here to see?

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

[Eranga]

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.

[Eranga]

Revisit this recursive invoke.

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.

[JosAH]

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

[Eranga]

Let see that op could grab it. ;)

[flyingcurry]

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!

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;
	}

[flyingcurry]

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.

[JosAH]

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:

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

[flyingcurry]

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));"

[JosAH]

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

[flyingcurry]

Thanks, that was very helpful!