# Why did I get stack overflow in my program?

• ``````public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
//log n algorithm we need a tree structure
//no time to construct a tree as takes O(m+n)
//sorted array they are bst
//3 4 5  A
//6 7      B
if(A.length>B.length){
return findMRecursive(B,0,B.length-1,A,0,A.length-1);
}
else{
return findMRecursive(A,0,A.length-1,B,0,B.length-1);
}
}

public double findMRecursive(int A[],int startA,int endA, int B[],int startB,int endB){
//deal with some base cases:
//A = 0,B = 0
//A = 0,B !=0
if(endA==-1){
return B[(endB-startB)/2];
}
//A = 1, B = 1
if(startA==endA && startB==endB){
return (A[startA] + B[startB])/2;
}
//A = 1, B = odd
if(startA==endA && (endB - startB)%2==0){
int mid = (endB - startB)/2;
return (B[mid] + mo3(A[startA],B[mid-1],B[mid+1]))/2;
}
//A = 1, B = even
if(startA==endA && (endB - startB)%2==1){
int mid = (endB - startB)/2;
return mo3(A[startA],B[mid],B[mid+1]);
}
//A = 2, B = 2
if(endA-startA==1 && endB-startB==1){
return mo4(A[startA],A[endA],B[startB],B[startB]);
}
//A = 2, B = odd
if(endA-startA==1 && (endB - startB)%2==0){
int mid = (endB - startB)/2;
return mo3(Math.min(A[startA],B[mid-1]),B[mid],Math.max(A[endA],B[mid+1]));
}
//A = 2, B = even
if(endA-startA==1 && (endB - startB)%2==1){
int mid = (endB - startB)/2;
return mo4(Math.min(A[startA],B[mid-1]),B[mid],B[mid+1],Math.max(A[endA],B[mid+2]));
}
//A is the longer array
//compare A median and B median
//if A > B then cut the left half of B
//if A <= B then cut the right half of
//and}then cut the same length of A in the opposite side
//do recursively
int midA = (endA - startA)/2;
int midB = (endB - startB)/2;

if(A[midA]>B[midB]){
return findMRecursive(A,startA,midA,B,startB+(endA-midA),endB);
}

return findMRecursive(A,midA,endA,B,startB,endB-(midA-startA));

}
//help funciton
public double mo3(int a,int b,int c){
return a+b+c-Math.max(Math.max(a,b),c) - Math.min(Math.min(a,b),c);
}

public double mo4(int a,int b,int c,int d){
int max = Math.max(Math.max(Math.max(a,b),c),d);
int min = Math.min(Math.min(Math.min(a,b),c),d);

return (a+b+c+d-max-min)/2;
}
``````

}

I got a runtime error stackoverflow in my program when encountered the input test case: [3 3 3 3],[3 3 3 3]. It said I got stack overflow here `return findMRecursive(A,0,A.length-1,B,0,B.length-1);`

Here is the idea of my algorithm: Assume A is the shorter array.
I have 7 base cases for the program

1. A = 0,B !=0
2. A = 1, B = 1
3. A = 1, B = odd
4. A = 1, B = even
5. A = 2, B = 2
6. A = 2, B = odd
7. A = 2, B = even

If the input is not in these base cases, I will compare the median of the two arrays and if medianA is the bigger one, I will cut the right side of array A and cut the left side of array B of the same length of the right side of array A. And put them into the recursion. if medianA is the smaller one, i will do the opposite. My algortihm takes O(log(n)+log(m))

• There is an infinite loop in your code for the input case [3 3 3 3], [3 3 3 3].

Consider the startA, endA, startB, endB values in the recursion.

First iteration: startA = 0, endA = 3, startB = 0, endB = 3. No problem.

Second iteration: startA = 1, endA = 3, startB = 0, endB = 2
Then midA = (3 - 1) / 2 = 1
The code will go to this branch

``````findMRecursive(A,midA,endA,B,startB,endB-(midA-startA));
``````

Third iteration: startA = 1, endA = 3, startB = 0, endB = 2 - (1 - 1) = 2

You see the parameters are exactly the same as those in round 2. The infinite loop begins.

• thank so much！

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.