The O(n) Club: Ditch the Merge—Median of Two Sorted Arrays with a Binary Search Side Quest

The O(n) Club: Ditch the Merge—Median of Two Sorted Arrays with a Binary Search Side Quest

⚡ TL;DR

Yes, you can get the median of two sorted arrays—without the time-honored mess of merging and re-sorting everything like it’s 1999. Use binary search on the smaller array, play partition ninja, and boom: O(log(m+n)) time. Here’s the old-school ‘please don’t do this’ Java solution for reference:

// Brute force way (not optimal):
int[] merged = new int[nums1.length + nums2.length];
System.arraycopy(nums1, 0, merged, 0, nums1.length);
System.arraycopy(nums2, 0, merged, nums1.length, nums2.length);
Arrays.sort(merged);
int n = merged.length;
double median = (n % 2 == 0) ? (merged[n/2 - 1] + merged[n/2]) / 2.0 : merged[n/2];

🧠 How Devs Usually Mess This Up

Every junior dev’s gut instinct: just mash up both arrays, sort, and ping the halfway point. Sure, if you’re writing code for fruit flies (who die before your O(m+n) slog is done). Some brave souls start doing binary search on both arrays or forget the little detail that ‘median’ isn’t always a single value if the combined count is even. Bonus drama: Dying on edge cases when arrays are empty, or when indices throw tantrums. Tough love, but we’ve all written code that panics at nums1[-1].

🔍 What’s Actually Going On

Visual time: Think of two bakery conveyor belts (arrays)—pastries lined up in size order, and you’re hungry for the absolute middle bite. But you can’t dump both conveyor belts together, or the health inspector (your interviewer) will write up a ticket. Instead, use binary search on the smaller belt, adjust where the imaginary spatula slices each, and check if everything to the left of your cuts is less than or equal to everything on the right. Partition just right? Conga line to that median.

🛠️ PseudoCode

• Make sure you’re searching the smaller array

  if (nums1.length > nums2.length) swap(nums1, nums2);

  No one wants to debug index math on the bigger one.

• Fire up your binary search

  left = 0, right = nums1.length;

  The fencing begins.

• Bisection time

  while (left <= right):
      i = (left + right)/2
      j = (totalLength + 1)/2 - i;

  i and j are your virtual knives.

• Check the partition toppings

  nums1Left = (i == 0) ? -INF : nums1[i-1];
  nums1Right = (i == nums1.length) ? INF : nums1[i];
  nums2Left = (j == 0) ? -INF : nums2[j-1];
  nums2Right = (j == nums2.length) ? INF : nums2[j];

  Who knew infinity would finally be useful.

• If both left sides ≤ both right sides:

  if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
      if (totalLength % 2 == 0)
          median = (max(nums1Left, nums2Left) + min(nums1Right, nums2Right)) / 2.0;
      else
          median = max(nums1Left, nums2Left);
  }

  There it is, the Holy Median Grail.

• Otherwise, shift your search

  if (nums1Left > nums2Right) right = i - 1;
  else left = i + 1;

  Move the spatula, try again.

💻 The Code

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        int[] temp = nums1; nums1 = nums2; nums2 = temp;
    }
    int m = nums1.length, n = nums2.length;
    int total = m + n;
    int left = 0, right = m;
    while (left <= right) {
        int i = (left + right) / 2;
        int j = (total + 1) / 2 - i;
        int nums1Left = (i == 0) ? Integer.MIN_VALUE : nums1[i-1];
        int nums1Right = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int nums2Left = (j == 0) ? Integer.MIN_VALUE : nums2[j-1];
        int nums2Right = (j == n) ? Integer.MAX_VALUE : nums2[j];
         if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
            if (total % 2 == 0) {
                return (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2.0;
            } else {
                return (double) Math.max(nums1Left, nums2Left);
            }
        } else if (nums1Left > nums2Right) {
            right = i - 1;
        } else {
            left = i + 1;
        }
    }
    throw new IllegalArgumentException("Input arrays not sorted or invalid");
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Always search the smaller array. Binary search on the big guy means six hours of debugging and one existential crisis.
• Don’t freak out if one array is empty—the code above actually handles it. Lesser codebases do not.
• Even number of elements? Median isn’t just the guy in the middle—average the two centermost values.
• Negative indices and empty halves: -INFINITY and INFINITY can be your imaginary array bouncers.
• Time: O(log(min(m, n))). Space: O(1). Fast, lean, and caffeine-friendly.

🧠 Interviewer Brain-Tattoo

Why sort it twice when it’s already sorted once? Go partition, not postal.