title: Algorithm : Median of two sorted array of different sizes
body: <p>Here is a code pasted from <a href="http://leetcode.com/2011/03/median-of-two-sorted-arrays.html#comment-1053" rel="nofollow">here</a></p>
  
  <p>I'm unable to understand what it is doing. I could think of a simple algorithm to find median of two sorted arrays when merged. The idea is to compare the medians (m1, m2) of both the arrays and if <code>m1 &lt; m2</code> find median of right first subarray from m1 and left second subarray upto m2. The following code is doing it in the same lines but I'm unable to understand it completely.</p>
  
  <pre><code>double findMedian(int A[], int B[], int l, int r, int nA, int nB) {
      if (l&gt;r)
          return findMedian(B, A, max(0, (nA+nB)/2-nA), min(nB, (nA+nB)/2), nB, nA); //What does the min/max do here
      int i = (l+r)/2;
      int j = (nA+nB)/2 – i – 1;
      if (j&gt;=0 &amp;&amp; A[i] &lt; B[j])
          return findMedian(A, B, i+1, r, nA, nB);
      else if (j&lt;nB-1 &amp;&amp; A[i] &gt; B[j+1])
          return findMedian(A, B, l, i-1, nA, nB);
      else {
          if ( (nA+nB)%2 == 1 ) return A[i];
          else if (i&gt;0) return (A[i]+max(B[j], A[i-1]))/2.0; //I couldn't understand this
          else return (A[i]+B[j])/2.0;
      }
  }
  
  double findMedianSortedArrays(int A[], int n, int B[], int m) {
      if (n&lt;m)
          return findMedian(A, B, 0, n-1, n, m);
      else
          return findMedian(B, A, 0, m-1, m, n);
  }
  </code></pre>
  
  <p>What does the second line of the code do? Apart from that I couldn't comprehend how the last <code>else</code> block will return a median. will <code>i</code> index contain the median when <code>n + m</code> is odd?</p>
  
  <p>Any help, links or pointers are appreciated. </p>