Problem
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Analysis
Analysis
Median is middle element in sorted array. So it is the (A'length + B'length)/2 of combined array of A and B. It can be solved by using K'th element where K is (A'length + B'length)/2
JavaScript code
function findMedianSortedArrays(A, B) { var m = A.length; var n = B.length; if ((m + n) % 2 != 0) // odd return findKth(A, B, parseInt((m + n) / 2), 0, m - 1, 0, n - 1); else { // even return (findKth(A, B, parseInt((m + n) / 2), 0, m - 1, 0, n - 1) + findKth(A, B, parseInt((m + n) / 2) - 1, 0, m - 1, 0, n - 1)) * 0.5; } } function findKth(A, B, k, aStart, aEnd, bStart, bEnd) { var aLen = aEnd - aStart + 1; var bLen = bEnd - bStart + 1; // Handle special cases if (aLen == 0) return B[bStart + k]; if (bLen == 0) return A[aStart + k]; if (k == 0) return A[aStart] < B[bStart] ? A[aStart] : B[bStart]; var aMid = parseInt(aLen * k / (aLen + bLen)); // a's middle count var bMid = parseInt(k - aMid - 1); // b's middle count // make aMid and bMid to be array index aMid = aMid + aStart; bMid = bMid + bStart; if (A[aMid] > B[bMid]) { k = k - (bMid - bStart + 1); aEnd = aMid; bStart = bMid + 1; } else { k = k - (aMid - aStart + 1); bEnd = bMid; aStart = aMid + 1; } return findKth(A, B, k, aStart, aEnd, bStart, bEnd); } console.log(findMedianSortedArrays([1,2,8,10],[5,6,7,8]));
Aluminum Scandium Sputtering Target - Alfa Chemistry can provide testing in the laboratory, small dose testing, pilot test.
ReplyDelete