Find Median In Two Sorted Arrays

This is same as finding kth smallest element in two sorted arrays, just trying to find one or two middle numbers and compute the median out of them. As demonstrated in another post.

Here's a more elegant algorithm than what I have posted. I want to put here and do some analysis on it. With minor change, this will become kth smallest element in two sorted arrays.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public static double findMedianSortedArrays(int[] A, int[] B) { int n = A.length; int m = B.length; if (n > m) return findMedianSortedArrays(B, A); // shorter array first //trick: in 0 based array, the middle point is (length-1)/2 int k = (n + m - 1) / 2; // mid position, thinking in 0 based index //define l and r as left and right boundary index in A //since we are talking about index, so both k and n need minus 1 in 0 based index int l = 0, r = Math.min(k-1, n-1); // r is right boundary in A //narrow down the search range in A while (l < r) { int midA = l + (r - l+1) / 2; // r-l+1 is important step. this is same as //trick mentioned above. since now r is index, so r+1 is length int midB = k - midA; // if midA is lower valid index, all elements before it are within smallest k //then what left in B is about k-midA if (A[midA] < B[midB]) l = midA + 1; //element before midA has been determined, then check next left boundary else r = midA; // l, i } // A[l-1], A[l], B[k-l], and B[k-l+1] int a = Math.max(l > 0 ? A[l - 1] : Integer.MIN_VALUE, k - l >= 0 ? B[k - l] : Integer.MIN_VALUE); if ((n + m) % 2 == 1) return (double) a; // odd int b = Math.min(l > n ? A[l] : Integer.MAX_VALUE, k - l + 1 < m ? B[k - l + 1] : Integer.MAX_VALUE); return (a + b) / 2.0; // even }