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.

I am kind of stuck on the logic of this binary recursive algorithm.
I know there is errors with the code but I just don't know what errors, and how I am thinking about this wrong.

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 -1;
		if (array[end]>array[start])
			return(array[end]);
		if (array [start]>array[end])
			return (array[start]);

		int mid= (start+end)/2;
		return findMaxInt(array, start, mid);
		return findMaxInt(array, mid+1, end);

	}

Updated, I tried some thing new, but there are still some errors with the logic.

public static void findMaxInt (int []array, int start, int end){

		if (array.length==0)
			System.out.println(Integer.MIN_VALUE);

		int curmax1, curmax2, curmax;
		if (start>end)
			return;

		int mid= (start+end)/2;

		curmax1=findMaxInt(array, start, mid);
		curmax1=findMaxInt(array, mid+1, end);

		if (curmax1>curmax2)
			curmax=curmax1;
		else
			curmax=curmax2;
	}

You are on the right track. What you really need to work on is your base case. The function should also return an integer in order to be recursive, or you won't be able to compare value returned from the deeper level function call. In this case, there should be around 3 base cases - when array length is 0 (return MIN_VALUE), end is greater than or equal to start (return value of arr at start), and end is greater than start by 1 (return value at whichever is greater). You still have to keep both search left & right as you are doing now, and return whatever is greater.

Edited 6 Years Ago by Taywin: n/a

The function should also return an integer in order to be recursive, or you won't be able to compare value returned from the deeper level function call. In this case, there should be around 3 base cases - when array length is 0 (return MIN_VALUE), end is greater than or equal to start (return value of arr at start), and end is greater than start by 1 (return value at whichever is greater). You still have to keep both search left & right as you are doing now, and return whatever is greater.

Thanks for the advice, i got the program compiling now, but I keep on getting a "Exception in thread "main" java.lang.StackOverflowError".

Here is my updated method:

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

	}

The stack overflow is caused by calling findMaxInt in an infinite loop, and it is from your 'mid' value. Whenever your start & end is 1 different, you keep creating the call. That's why I said in my earlier post that you need 3 base cases. You are missing the case when start & end are 1 different (only 2 value in the array left).

Also, your first findMaxInt should print it out instead of plainly call the other findMaxInt.

// this one
public static void findMaxInt (int [] array) {
  findMaxInt(array, 0, array.length-1);
}
// should be
public static void findMaxInt (int [] array) {
  System.out.println(findMaxInt(array, 0, array.length-1));
}

// The base cases are mutually exclusive. In other words, they must be
// satisfied only one of these, or do nothing.
if (array.length==0)
  return Integer.MIN_VALUE;  // must satisfy the return type, not just stop
else if (start>end)
  return array[start];
else if ((end-start)==1) {  // now you have only 2 values to compare
  if (array[start]>array[end]) { return array[start]; }
  else { return array[end]; }
}

// And as I said earlier, you should keep the way you find currMax1 and currMax2.
// Keep them the way you did before, but instead of assigning to another variable
// currMax, return the value of the either currMax1 or currMax2 instead.

// And as I said earlier, you should keep the way you find currMax1 and currMax2.
// Keep them the way you did before, but instead of assigning to another variable
// currMax, return the value of the either currMax1 or currMax2 instead.

I switched back to currMax1, and currMax2, and i realized that i should have changed "else if (start>end)" to "else if (start>=end)". It seems to work fine now.

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

Thanks for your help!!

Edited 3 Years Ago by pritaeas: Fixed formatting

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(SingleByteEncoder.java:95)
at sun.nio.cs.SingleByteEncoder.encodeLoop(SingleByteEncoder.java:134)
at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:544)
at sun.nio.cs.StreamEncoder$CharsetSE.implWrite(StreamEncoder.java:384)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:136)
at java.io.OutputStreamWriter.write(OutputStreamWriter.java:191)
at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:111)

I don't know how else to return the "Integer.MIN_VALUE".

Change curmax2=findMaxInt(array, mid+1, end); to curmax2=findMaxInt(array, mid, end); and change mid=(start+end)/2; to mid=(start+end+1)/2;?

Edited 6 Years Ago by Taywin: n/a

Change curmax2=findMaxInt(array, mid+1, end); to curmax2=findMaxInt(array, mid, end); and change mid=(start+end)/2; to mid=(start+end+1)/2;?

Why is it curmax2=findMaxInt(array, mid, end), rather than curmax2=findMaxInt(array, mid+1, end)?
My understanding was that the array[mid] will be compared with twice if it's curmax2=findMaxInt(array, mid, end)?

Because the code is not optimal in this case. :) Your code should work though. I am still thinking about how you actually call the function when the array is length 0? The problem may lie in findMaxInt(array, 0, array.length-1); because the 'end' is -1 instead of 0. Then, in your first base case, you use System.out.println instead of return the value! You need to return it instead of print it out.

Edited 6 Years Ago by Taywin: n/a

This article has been dead for over six months. Start a new discussion instead.