SimuVedaAlgorithms Lab Open in the lab

Searching / Intermediate

Median of Two Sorted Arrays Visualizer

Cut the shorter array at i and the longer at j so the two left parts hold half of all values. The cut is right when every left value ≤ every right value: A[i−1] ≤ B[j] and B[j−1] ≤ A[i]. Binary-search i until that holds; the median sits at the cut.

Start the Median of Two Sorted Arrays simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(log min(m, n))
Worst timeO(log min(m, n))
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Indexes 0 to 4 are the shorter array A, the rest is B. The left half must hold 6 of the 11 values. [1, 3, 8, 9, 15, 7, 11, 18, 19, 21, 25]
  2. Try i = 2 from A and j = 6 − 2 = 4 from B for the left half.
  3. At the cut: A left 3, A right 8, B left 19, B right 21.
  4. B left 19 > A right 8: A gives too few values. Move the cut in A right.
  5. Try i = 4 from A and j = 6 − 4 = 2 from B for the left half.
  6. At the cut: A left 9, A right 15, B left 11, B right 18.
  7. 9 ≤ 18 and 11 ≤ 15: a valid cut. 11 is odd, so the median is the biggest left value, 11.

Try it with your own input →

Median of two sorted arrays in Java, Python, C++, C and JavaScript

double findMedian(int[] A, int[] B) {   // A is the shorter
  int m = A.length, n = B.length, half = (m + n + 1) / 2;
  int lo = 0, hi = m;
  while (lo <= hi) {
    int i = (lo + hi) / 2, j = half - i;
    int aL = i > 0 ? A[i-1] : MIN, aR = i < m ? A[i] : MAX;
    int bL = j > 0 ? B[j-1] : MIN, bR = j < n ? B[j] : MAX;
    if (aL <= bR && bL <= aR)
      return (m + n) % 2 == 1 ? Math.max(aL, bL)
           : (Math.max(aL, bL) + Math.min(aR, bR)) / 2.0;
    if (aL > bR) hi = i - 1; else lo = i + 1;
  }
  return 0;
}
def find_median(A, B):  # A is the shorter
    m, n = len(A), len(B)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2; j = half - i
        aL = A[i-1] if i > 0 else float('-inf')
        aR = A[i] if i < m else float('inf')
        bL = B[j-1] if j > 0 else float('-inf')
        bR = B[j] if j < n else float('inf')
        if aL <= bR and bL <= aR:
            if (m + n) % 2 == 1:
                return max(aL, bL)
            return (max(aL, bL) + min(aR, bR)) / 2
        if aL > bR:
            hi = i - 1
        else:
            lo = i + 1
    return 0
double findMedian(const vector<int>& A, const vector<int>& B) {  // A is the shorter
  int m = A.size(), n = B.size(), half = (m + n + 1) / 2;
  int lo = 0, hi = m;
  while (lo <= hi) {
    int i = (lo + hi) / 2, j = half - i;
    int aL = i > 0 ? A[i-1] : INT_MIN, aR = i < m ? A[i] : INT_MAX;
    int bL = j > 0 ? B[j-1] : INT_MIN, bR = j < n ? B[j] : INT_MAX;
    if (aL <= bR && bL <= aR)
      return (m + n) % 2 == 1 ? max(aL, bL)
           : (max(aL, bL) + min(aR, bR)) / 2.0;
    if (aL > bR) hi = i - 1; else lo = i + 1;
  }
  return 0;
}
#include <limits.h>
#define MAX2(x, y) ((x) > (y) ? (x) : (y))
#define MIN2(x, y) ((x) < (y) ? (x) : (y))

double findMedian(int A[], int m, int B[], int n) {  // A is the shorter
  int half = (m + n + 1) / 2;
  int lo = 0, hi = m;
  while (lo <= hi) {
    int i = (lo + hi) / 2, j = half - i;
    int aL = i > 0 ? A[i-1] : INT_MIN, aR = i < m ? A[i] : INT_MAX;
    int bL = j > 0 ? B[j-1] : INT_MIN, bR = j < n ? B[j] : INT_MAX;
    if (aL <= bR && bL <= aR)
      return (m + n) % 2 == 1 ? MAX2(aL, bL)
           : (MAX2(aL, bL) + MIN2(aR, bR)) / 2.0;
    if (aL > bR) hi = i - 1; else lo = i + 1;
  }
  return 0;
}
function findMedian(A, B) {  // A is the shorter
  const m = A.length, n = B.length, half = Math.floor((m + n + 1) / 2);
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = Math.floor((lo + hi) / 2), j = half - i;
    const aL = i > 0 ? A[i-1] : -Infinity, aR = i < m ? A[i] : Infinity;
    const bL = j > 0 ? B[j-1] : -Infinity, bR = j < n ? B[j] : Infinity;
    if (aL <= bR && bL <= aR)
      return (m + n) % 2 === 1 ? Math.max(aL, bL)
           : (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
    if (aL > bR) hi = i - 1; else lo = i + 1;
  }
  return 0;
}

In an interview

LeetCode 4, Median of Two Sorted Arrays, in O(log(m + n)): one of the hardest classic binary searches.

Search the shorter array so j never goes out of range. Treat a missing neighbour past an end as −∞ or +∞. Merging is the easy O(m + n) answer; mention it first.

More searching