Median of two sorted Arrays

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))

Two Sorted Arrays of Equal Length:
http://www.geeksforgeeks.org/median-of-two-sorted-arrays/

Two Sorted Arrays of Un-Equal Length:
http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/
http://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/
http://www.leetcode.com/2011/03/median-of-two-sorted-arrays.html

Question on Medians:
1.Find the kth smallest in union of two sorted arrays

www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

http://anandtechblog.blogspot.in/2011/06/google-interview-find-kth-smallest-from.html

Best Method
Let us first take the k/2th element of both the arrays(say array S1 and S2). If k/2th element of array S1 is greater than the k/2th element of S2 but smaller than (k/2 + 1) element of S2, then k/2th element of array S1 is the answer. (Vice versa is also true)
If k/2th element of S1 is greater than both k/2 and (k/2 + 1) element of S2, then consider 3k/4th (k/2 + k/4) element of S2 and k/4th (k/2-k/4) element of S1 and compare them in the fashion described above(If the element under consideration of one array is greater than the element under consideration of another array but less than the +1 element, then it is the answer).
Each time, increase the pointer of one array by k/(2^i) and decrease the pointer of the other array by k/(2^i) (i is the number of iteration) till the above condition is satisfied.
This way you can find kth element in O(log n) time

Example:
Array S1: 5, 7, 8, 9, 12
Array S2: 3, 10, 11, 14, 15
We need 4th smallest element.
First iteration. 4/2 which is 2nd element of both arrays are considered.
7 < 10 and 8 < 10.
So increase the pointer of S1 by 4/4 ie 3rd position and decrease the pointer of S2 by 4/4 ie 1.
8 > 3 and 8 < 10 and hence 8 is the answer in this case.

Method of Two Pointers:O(n)
int getMedian(int ar1[], int ar2[], int n)
{
  int i = 0;j = 0;count;
  int m1 = -1, m2 = -1;

 for(count = 0; count <= n; count++)
  {
//Case to handle where all elements of one array is smaller than other
    if(i == n)
    {
      m1 = m2;
      m2 = ar2[0];
      break;
    }
   else if(j == n)
    {
      m1 = m2;
      m2 = ar1[0];
      break;
    }

//Actual Comparison
    if(ar1[i] < ar2[j])
    {
      m1 = m2;
      m2 = ar1[i];
      i++;
    }
    else
    {
      m1 = m2;
      m2 = ar2[j];
      j++;
    }

  }   //End of for
  return (m1 + m2)/2;
}

Method of Comparing Medians:O(logn)
int max(int x, int y)
{
    return x > y? x : y;
}
int min(int x, int y)
{
    return x > y? y : x;
}
int median(int arr[], int n)
{
  if(n%2 == 0)
    return (arr[n/2] + arr[n/2-1])/2;
  else
    return arr[n/2];
}

int getMedian(int ar1[], int ar2[], int n)
{
  int m1;
  int m2;

  if(n <= 0)
    return -1;

  if(n == 1)
    return (ar1[0] + ar2[0])/2;

  if (n == 2)
    return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;

  m1 = median(ar1, n);
  m2 = median(ar2, n);

  if(m1 == m2)
    return m1;

  if (m1 < m2)
    return getMedian(ar1 + n/2, ar2, n - n/2);

  return getMedian(ar2 + n/2, ar1, n - n/2);
}

Method of Binary Search:O(logn)
int getMedianRec(int ar1[], int ar2[], int left, int right, int n)
{
  int i, j;
  /* We have reached at the end (left or right) of ar1[] */
  if(left > right)
    return getMedianRec(ar2, ar1, 0, n-1, n);

  i = (left + right)/2;
  j = n - i - 1;
 /* Recursion terminates here.*/
  if(ar1[i] > ar2[j] && (j == n-1 || ar1[i] <= ar2[j+1]))
  {
     if(ar2[j] > ar1[i-1] || i == 0)
       return (ar1[i] + ar2[j])/2;
     else
       return (ar1[i] + ar1[i-1])/2;
  }

  else if (ar1[i] > ar2[j] && j != n-1 && ar1[i] > ar2[j+1])
    return getMedianRec(ar1, ar2, left, i-1, n);        
  else
    return getMedianRec(ar1, ar2, i+1, right, n);
}

int getMedian(int ar1[], int ar2[], int n)
{
  return getMedianRec(ar1, ar2, 0, n-1, n);
}

Problems on Median of two sorted arrays:
1.Tournament Tree- http://www.geeksforgeeks.org/archives/11556
2.Median in a stream of numbers- http://geeksforgeeks.org/forum/topic/fining-the-median
3.kth smallest in union of two sorted array--http://geeksforgeeks.org/forum/topic/kth-smallest-element-in-the-union-of-the-arrays-in-a-logarithmic-time-algorithm
4.Quick Sort-Suggest a partition approach that reduces worst case complexity to O(n log n)-http://geeksforgeeks.org/forum/topic/quick-sort-in-worst-case-onlogn-1