Skip to content

Instantly share code, notes, and snippets.

@aire-con-gas
Created December 8, 2017 18:13
Show Gist options
  • Select an option

  • Save aire-con-gas/bc0cf75ed64f740d52aa0ef1cd43b0d2 to your computer and use it in GitHub Desktop.

Select an option

Save aire-con-gas/bc0cf75ed64f740d52aa0ef1cd43b0d2 to your computer and use it in GitHub Desktop.
find median of two sorted arrays
const median = (A = [], B = []) => {
const m = A.length;
const n = B.length;
let iMin = 0;
let iMax = m;
let halfLength = Math.floor((m + n + 1) / 2);
let result = -1;
console.log('******* START ******');
console.log('A', A);
console.log('B', B);
console.log('halfLength', halfLength);
while (iMin <= iMax) {
console.log('---- LOOP ----');
console.log('iMin', iMin);
console.log('iMax', iMax);
let i = Math.floor((iMin + iMax) / 2);
let j = halfLength - i;
console.log('i', i);
console.log('j', j);
if (i < m && B[j-1] > A[i]) {
// if the pointer i is less than the length of array A
// and the value of B[j-1] is greater than
// A[i]
iMin = i + 1;
} else if (i > 0 && A[i-1] > B[j]) {
iMax= i - 1;
} else {
let maxOfLeft;
let minOfRight;
if (i === 0) {
maxOfLeft = B[j-1];
} else if (j === 0) {
maxOfLeft = A[i-1];
} else {
maxOfLeft = Math.max(A[i-1], B[j-1]);
}
if ((m + n) % 2 === 1) {
result = maxOfLeft;
break;
}
if (i === m) {
minOfRight = B[j];
} else if (j === n) {
minOfRight = A[i];
} else {
minOfRight = Math.min(A[i], B[j]);
}
result = Math.floor((maxOfLeft + minOfRight) / 2);
break;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment