Geek asks and answers

Find median of two sorted arrays - I get stackoverflow exception

The task is set two sorted Arrays, find medianout of two c O(log n). merging sorted arrays and finding the median (at n / 2) should work. But this is the O(n)time that I assume, and this requires auxiliary storage. I found this pseudo code (problem 2 in pdf). when i implement this code i get stackoverflow exception. Here is my code:

public static int quickMedian(int[] arr1, int[] arr2, int startArr1, int endArr1, int startArr2, int endArr2){  
        int m1=(endArr1-startArr1)/2;
        int m2=(endArr2-startArr2)/2;
        if (arr1[m1]==arr2[m2])
            return arr1[m1];
        if (arr1[m1]<arr2[m2])
            return quickMedian(arr1, arr2, m1, endArr1, startArr2, m2);
        else 
            return quickMedian(arr1, arr2, startArr1, m1, m2, endArr2);
    }

public static void main (String[] args){
        int[] arr1={1,3,5,7};
        int[] arr2={2,4,6,8};
        int[] arr3={1,2,4,6,8,10,11};
        System.out.println(quickMedian(arr1, arr2, 0, arr1.length-1, 0, arr2.length-1));
    }

I need help installing stackoverflow exceptionand do this job. Thank.

+3
source share
3 answers

The problem is the final condition

if (arr1[m1]==arr2[m2])
        return arr1[m1];

, . quickMedian() , .

EDIT:

, , . , , , , , .

, , , , , , , . , , , .

a1 = {1,2,3,4,6,7,8,9}    median = 6
a2 = {5}                  median = 5

// median of a1 + a2 is 5

:

a3 = {1,2,3,4}            median = 3
a4 = {5}                  median = 5

// median of a3 + a4 is 3

a3 + a4 3, , 5, , . , , , . , , . .

+2

PDF, ( ).

, , ?

:

quickMedian({1,3,5,7}, {2,4,6,8}, 0, 3, 0, 3)

quickMedian: (1)

m1 = (3 - 0) / 2 = 1
m2 = (3 - 0) / 2 = 1
if (3 == 4)...// false
if (3 < 4) quickMedian({1,3,5,7}, {2,4,6,8}, 1, 3, 0, 1)
else...// unreached

quickMedian: (2)

m1 = (3 - 1) / 2 = 1
m2 = (1 - 0) / 2 = 0
if (3 == 2)...// false
if (3 < 2)...// false
else quickMedian({1,3,5,7}, {2,4,6,8}, 1, 1, 0, 1)

quickMedian: (3)

m1 = (1 - 1) / 2 = 0
m2 = (1 - 0) / 2 = 0
if (1 == 2)...// false
if (1 < 2) quickMedian({1,3,5,7}, {2,4,6,8}, 0, 1, 0, 0)
else...// unreached

quickMedian: (4)

m1 = (1 - 0) / 2 = 0
m2 = (0 - 0) / 2 = 0
if (1 == 2)...// false
if (1 < 2) quickMedian({1,3,5,7}, {2,4,6,8}, 0, 1, 0, 0)
else...// unreached

, quickMedian 4- quickMedian, . .

" , ", . - O (n), O (log n) .

+1

O((logN)^2) : -

  • , ,
  • s k- , ,
  • known = kold - s .
  • 1 , k- O (1).

: -

void medianSearch(arr1,arr2,s1,s2,h1,h2,k) {

  len1 = h1-s1+1;
  len2 = h2-s2+1;

  if(len1<=0||len2<=0) {

     if(len2<=0) {
           return(arr1[s1+k-1]);
     }

     else return(arr2[s2+k-1]);
  }

  if(len1>len2) {

     int mid = (s1+h1)/2
     int i = binSearch(arr2,s2,h2,arr1[mid])
     int size = i+mid-s1+2;
     if(size>=k) {
         return(medianSearch(arr1,arr2,s1,s2,mid,i,k))
     }
     else {

        return(medianSearch(arr1,arr2,mid+1,i+1,h1,h2,k-size));
     }
  }

  else {

      // Use similar logic as first case. 
  }

}

Call:- medianSearch(arr1,arr2,0,0,M-1,N-1,(M+N)/2)

: -

Each iteration reduces at least one array to half its orignal size. Each iteration takes O (logN). Total iterations will be O (logN), therefore T (N) = O ((logN) ^ 2)

0
source

More articles:


All Articles