# Runtime error, when inputing a long array

• ``````    class Solution {
public:
double searchKinTwo(int *array1, int *array2, int K, int l1, int r1, int l2, int r2)
{
//printf("%d %d %d %d %d\n",K,l1,r1,l2,r2);
// first handle one of the array is empty
if(r2<l2)
return 1.0*array1[K-1];
if(r1<l1)
return 1.0*array2[K-1];

if(K==1)
{
if(l1==-1) return array2[l2];
if(l2==-1) return array1[l1];
return array1[l1]>array2[l2]?array2[l2]:array1[l1];
}

if(r2==l2&&r1==l1)
{
if(array1[l1]<array2[l2])
return K==1?array1[l1]:array2[l2];
else
return K==1?array2[l2]:array1[l1];
//return (array1[l1]+array2[l2])/2.0;
}
int L1=-1, L2 = -1;
int m1 = ((r1)+(l1))>>1;
int m2 = ((r2)+(l2))>>1;
L1 = m1-l1;
L2 = m2-l2;
int L;

// need to compare median
double med1,med2;
if ((r1-l1+1)%2==1||l1==r1) med1 = array1[m1];
else med1 = (array1[m1]+array1[m1+1])/2.0;
if ((r2-l2+1)%2==1||l2==r2) med2 = array2[m2];
else med2 = (array2[m2]+array2[m2+1])/2.0;

if(med1<med2)
{
L = L1;
return searchKinTwo(array1, array2, K-L-1, m1+1, r1, l2, m2);
}
else if (med1>med2)
{
L = L2;
return searchKinTwo(array1, array2, K-L-1, l1, m1, m2+1, r2);
}
else
{
return med1;
}
}

double findMedianSortedArrays(int A[], int m, int B[], int n)
{
int flag;
if ((m+n)%2==0) flag = 0;
else flag = 1;

int K = (m+n)>>1;

if(flag==1) K++;

if(flag==0)
return searchKinTwo(A,B,K,0,m-1,0,n-1);// + searchKinTwo(A,B,K+1,0,m-1,0,n-1))/2.0;
else
return searchKinTwo(A,B,K,0,m-1,0,n-1);
}

};
``````

Attached is my code, it meets runtime error, where could it be?

• Hi, I recursively search the Kth element in two array by finding each array's median and delete those outside the range [median_low and median_high]

• My algorithm runs in O(m+n) and it is accepted. My idea is to find kth smallest number if array A and B are merged. Lets say A.length=m and B.length=n, here are 2 cases:

1. if (m+n) is odd, find kth smallest number where k=(m+n)/2+1;

2. if (m+n) is even, then the result is the average of two kth
smallest numbers with k1=(m+n)/2 and k2=(m+n)/2+1 respectively

``````    public double findKthNumber(int[]A, int[]B, int m, int n, int k){
int i=0;
int j=0;
int count=0;
int result=0;
while(i<m && j<n){
if(A[i]<=B[j]){
result=A[i++];
}
else{
result=B[j++];
}

if(++count==k){
return result;
}
}
if(i==m){
return B[j+k-count-1];
}
else{
return A[i+k-count-1];
}
}
``````

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