### 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]));
```

#### 1 comment:

1. Aluminum Scandium Sputtering Target - Alfa Chemistry can provide testing in the laboratory, small dose testing, pilot test.