Central Median from Dual Sorted Lists

You're in a Google phone screen, and the interviewer asks: "Given two sorted arrays, find their combined median in better than linear time." The room goes quiet. This problem has a reputation, and for good reason. It's one of the hardest binary search problems you'll encounter, with a 42% acceptance rate and frequent appearances at Google (27 times), Uber (18 times), and Amazon (14 times). The trick is that you never actually merge the arrays.

TL;DR

Use binary search on the shorter array to find a partition that splits both arrays into left and right halves, where every element on the left is less than or equal to every element on the right. For odd total lengths, the median is the max of the left side. For even totals, it's the average of the left-side max and the right-side min. This runs in O(log(min(m, n))) time and O(1) space because you only search through the smaller array.

Why This Problem Matters

Finding the median of two sorted arrays sits at the intersection of binary search and divide-and-conquer, two categories that come up constantly in technical interviews. It's rated difficulty 83 on Firecode and is genuinely hard. Most candidates can describe the brute-force merge approach, but the logarithmic solution requires a conceptual leap: instead of merging, you search for the right partition point. That shift in thinking is what interviewers are testing.

The Brute Force (And Why It Falls Short)

The straightforward approach is to merge both sorted arrays into one and pick the middle element. This works, but it runs in O(m + n) time and O(m + n) space. The problem explicitly asks for O(log(m + n)), which rules out any linear scan.

Here is the insight that makes logarithmic time possible: you don't need the full merged array. You only need to know which elements would be on the left half and which would be on the right. Binary search can find that boundary without touching every element.

The Partition Strategy

Think of the median as a dividing line. If you had all m + n elements sorted, the median sits right in the middle. Our job is to find where that middle falls across the two arrays, without actually merging them.

The approach works like this:

1. Always binary search on the shorter array (call it nums1). This keeps the search space minimal.
2. For any partition point p1 in nums1, the corresponding partition point p2 in nums2 is determined: p2 = (m + n + 1) / 2 - p1. Together, p1 + p2 elements land on the left side.
3. A partition is valid when the largest element on the left side of each array is less than or equal to the smallest element on the right side of the other array.

Here's the high-level flow:

The partition is valid when maxLeft1 <= minRight2 and maxLeft2 <= minRight1. If maxLeft1 is too large, you've taken too many elements from nums1, so move the partition left. If maxLeft2 is too large, you haven't taken enough from nums1, so move it right.

Walkthrough: Example 1

For nums1 = [1, 3] and nums2 = [2], the combined sorted array would be [1, 2, 3]. The median is 2.0.

The binary search finds a valid partition on the first try. With partition1 = 1 and partition2 = 1, we get left side {1, 2} and right side {3}. Since the total length is odd (3 elements), the median is max(1, 2) = 2.0.

Walkthrough: Example 2

For nums1 = [1, 2] and nums2 = [3, 4], the combined sorted array would be [1, 2, 3, 4]. The median is (2 + 3) / 2 = 2.5.

The first partition attempt fails because maxLeft2 = 3 > minRight1 = 2. We need more elements from nums1 on the left, so we increase low. The second attempt succeeds: left side {1, 2}, right side {3, 4}. Even total, so the median is (max(2, -INF) + min(INF, 3)) / 2 = 2.5.

Walkthrough: Negative Numbers

For nums1 = [-5, 3, 6] and nums2 = [-2, 4, 7], the combined sorted array would be [-5, -2, 3, 4, 6, 7]. The median is (3 + 4) / 2 = 3.5.

Negative numbers don't change the algorithm. The binary search adjusts the partition until maxLeft1 <= minRight2 and maxLeft2 <= minRight1 both hold, then computes the median from the boundary values.

Implementation

Prefer a different language? Jump to solutions in other languages.

Here's the Java implementation. The key details to pay attention to: we always search on the shorter array, we use sentinel values (Integer.MIN_VALUE and Integer.MAX_VALUE) for boundary partitions, and we handle the even/odd split separately when computing the final answer.

public class Solution {

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    // Always binary search on the smaller array
    if (nums1.length > nums2.length) {
      return findMedianSortedArrays(nums2, nums1);
    }

    int smallerLength = nums1.length;
    int largerLength = nums2.length;
    int low = 0;
    int high = smallerLength;

    while (low <= high) {
      int partition1 = (low + high) / 2;
      int partition2 = (smallerLength + largerLength + 1) / 2 - partition1;

      int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
      int minRight1 = (partition1 == smallerLength) ? Integer.MAX_VALUE : nums1[partition1];

      int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
      int minRight2 = (partition2 == largerLength) ? Integer.MAX_VALUE : nums2[partition2];

      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
        if ((smallerLength + largerLength) % 2 == 0) {
          return ((double)Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
        } else {
          return (double)Math.max(maxLeft1, maxLeft2);
        }
      } else if (maxLeft1 > minRight2) {
        high = partition1 - 1;
      } else {
        low = partition1 + 1;
      }
    }

    throw new IllegalArgumentException("Input arrays are not sorted.");
  }
}

Breaking Down the Code

Swap to ensure smaller array is first. If nums1 is longer, we recursively swap the arguments. This guarantees the binary search runs in O(log(min(m, n))).

Compute partition positions. partition1 is the number of elements taken from nums1 for the left half. partition2 is computed from the constraint that the left half must have exactly (m + n + 1) / 2 elements total.

Sentinel values at boundaries. When partition1 == 0, there's no element to the left of the partition in nums1, so we use Integer.MIN_VALUE as a stand-in that won't interfere with comparisons. Similarly, Integer.MAX_VALUE represents a nonexistent right boundary.

Validate the partition. The partition is correct when every left element is at most every right element. In practice, you only need to check the cross-array condition: maxLeft1 <= minRight2 and maxLeft2 <= minRight1.

Compute the median. For odd totals, the median is max(maxLeft1, maxLeft2). For even totals, average the left-side max with the right-side min.

Edge Cases

Before moving on to complexity analysis, here are the boundary conditions to think about:

1. One empty array: If nums1 is empty, the partition in nums1 is 0 and all elements come from nums2. The sentinel values handle this correctly.
2. Single-element arrays: [1] and [2] gives partition1 = 0 or 1, and the median is (1 + 2) / 2 = 1.5.
3. All elements in one array smaller: [1, 2, 3] and [7, 8, 9] - the partition lands at [1, 2, 3 | ] and [ | 7, 8, 9], giving median (3 + 7) / 2 = 5.0.
4. Duplicate elements: [1] and [1, 1, 1, ..., 1] - the algorithm handles duplicates naturally since the comparison operators are <=, not <.

Complexity Analysis

Time Complexity: O(log(min(m, n)))

Each iteration of the binary search halves the search range on the shorter array. All operations inside the loop (comparisons, arithmetic, boundary checks) are O(1). The total number of iterations is at most log(min(m, n)).

Space Complexity: O(1)

The algorithm uses a fixed number of variables (low, high, partition1, partition2, and four boundary values) regardless of input size. No auxiliary arrays or data structures are needed.

Compare this to the merge approach, which uses O(m + n) time and O(m + n) space. For two arrays of a million elements each, the binary search approach does roughly 20 iterations while the merge scans two million elements.

Common Pitfalls

Here are the mistakes that trip people up most often on this problem:

1. Forgetting to search on the shorter array. If you binary search on the longer array, it still works, but you lose the O(log(min(m, n))) guarantee and get O(log(max(m, n))) instead. Always swap first.

2. Wrong partition2 formula. The formula is partition2 = (m + n + 1) / 2 - partition1. The +1 in the numerator ensures the left side gets the extra element when the total is odd. Getting this wrong shifts the median by one position.

3. Missing sentinel values. When partition1 = 0, accessing nums1[partition1 - 1] is an array-out-of-bounds error. Sentinel values at Integer.MIN_VALUE and Integer.MAX_VALUE are required, not optional.

4. Confusing the adjustment direction. When maxLeft1 > minRight2, you've taken too many from nums1, so move high down. When maxLeft2 > minRight1, you've taken too few from nums1, so move low up. Swapping these creates an infinite loop.

Interview Tips

When you encounter this problem:

1. Start with the brute force. Mention the merge approach as O(m + n) to show you understand the problem. Then explain why the interviewer wants logarithmic time.

2. Draw the partition. Sketch two arrays with a dividing line through each. Label the four boundary values. This visual makes the cross-comparison logic clear.

3. Trace through a small example. Use [1, 3] and [2]. Walk through one or two iterations of the binary search to show the partition converging.

4. Call out edge cases proactively. Mention empty arrays and the sentinel value approach before the interviewer asks.

5. State the complexity clearly. O(log(min(m, n))) time, O(1) space. Explain why the min matters, not just log.

Key Takeaways

• Binary search on the shorter array finds the correct partition in O(log(min(m, n))) time without merging the arrays.
• The partition constraint is that maxLeft1 <= minRight2 and maxLeft2 <= minRight1. Violating the first means move left; violating the second means move right.
• Sentinel values (Integer.MIN_VALUE, Integer.MAX_VALUE) eliminate boundary checks by representing nonexistent elements that never interfere with comparisons.
• For odd totals, the median is max(maxLeft1, maxLeft2). For even totals, average the left-side max and the right-side min.
• Always swap arrays so the shorter one is the binary search target. This is the difference between O(log(min(m, n))) and O(log(max(m, n))).

Solutions in Other Languages

Python

class Solution:
    def find_median_sorted_arrays(self, nums1, nums2):
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        smaller_length = len(nums1)
        larger_length = len(nums2)
        low, high = 0, smaller_length

        while low <= high:
            partition1 = (low + high) // 2
            partition2 = (smaller_length + larger_length + 1) // 2 - partition1

            max_left1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
            min_right1 = float('inf') if partition1 == smaller_length else nums1[partition1]

            max_left2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
            min_right2 = float('inf') if partition2 == larger_length else nums2[partition2]

            if max_left1 <= min_right2 and max_left2 <= min_right1:
                if (smaller_length + larger_length) % 2 == 0:
                    return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
                else:
                    return float(max(max_left1, max_left2))
            elif max_left1 > min_right2:
                high = partition1 - 1
            else:
                low = partition1 + 1

        raise ValueError("Input arrays are not sorted or have invalid lengths.")

Python uses float('-inf') and float('inf') as sentinel values. The logic is identical to the Java version. Integer division uses // to avoid floating-point partition indices.

JavaScript

class Solution {
  findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) {
      return this.findMedianSortedArrays(nums2, nums1);
    }

    const smallerLength = nums1.length;
    const largerLength = nums2.length;
    let low = 0;
    let high = smallerLength;

    while (low <= high) {
      const partition1 = Math.floor((low + high) / 2);
      const partition2 = Math.floor((smallerLength + largerLength + 1) / 2) - partition1;

      const maxLeft1 = (partition1 === 0) ? Number.NEGATIVE_INFINITY : nums1[partition1 - 1];
      const minRight1 = (partition1 === smallerLength) ? Number.POSITIVE_INFINITY : nums1[partition1];

      const maxLeft2 = (partition2 === 0) ? Number.NEGATIVE_INFINITY : nums2[partition2 - 1];
      const minRight2 = (partition2 === largerLength) ? Number.POSITIVE_INFINITY : nums2[partition2];

      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
        if ((smallerLength + largerLength) % 2 === 0) {
          return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
        } else {
          return Math.max(maxLeft1, maxLeft2);
        }
      } else if (maxLeft1 > minRight2) {
        high = partition1 - 1;
      } else {
        low = partition1 + 1;
      }
    }

    throw new Error("Input arrays are not sorted.");
  }
}

JavaScript requires Math.floor() for integer division. Number.NEGATIVE_INFINITY and Number.POSITIVE_INFINITY serve as the sentinel values.

C++

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    double findMedianSortedArrays(std::vector<int> &nums1, std::vector<int> &nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int smallerLength = nums1.size();
        int largerLength = nums2.size();
        int low = 0, high = smallerLength;

        while (low <= high) {
            int partition1 = (low + high) / 2;
            int partition2 = (smallerLength + largerLength + 1) / 2 - partition1;

            int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
            int minRight1 = (partition1 == smallerLength) ? INT_MAX : nums1[partition1];

            int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
            int minRight2 = (partition2 == largerLength) ? INT_MAX : nums2[partition2];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((smallerLength + largerLength) % 2 == 0) {
                    return ((double)std::max(maxLeft1, maxLeft2) + std::min(minRight1, minRight2)) / 2;
                } else {
                    return (double)std::max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                high = partition1 - 1;
            } else {
                low = partition1 + 1;
            }
        }

        throw std::invalid_argument("Input arrays are not sorted.");
    }
};

C++ uses INT_MIN and INT_MAX from <climits>. The std::max and std::min functions from <algorithm> handle the boundary value comparisons.

Go

package solution

func (s *Solution) FindMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
        nums1, nums2 = nums2, nums1
    }

    smallerLength, largerLength := len(nums1), len(nums2)
    low, high := 0, smallerLength

    maxInt := int(^uint(0) >> 1)
    minInt := -maxInt - 1

    for low <= high {
        partition1 := (low + high) / 2
        partition2 := (smallerLength + largerLength + 1) / 2 - partition1

        maxLeft1 := minInt
        if partition1 != 0 {
            maxLeft1 = nums1[partition1-1]
        }

        maxLeft2 := minInt
        if partition2 != 0 {
            maxLeft2 = nums2[partition2-1]
        }

        minRight1 := maxInt
        if partition1 != smallerLength {
            minRight1 = nums1[partition1]
        }

        minRight2 := maxInt
        if partition2 != largerLength {
            minRight2 = nums2[partition2]
        }

        if maxLeft1 <= minRight2 && maxLeft2 <= minRight1 {
            if (smallerLength+largerLength)%2 == 0 {
                return (float64(max(maxLeft1, maxLeft2)) + float64(min(minRight1, minRight2))) / 2.0
            } else {
                return float64(max(maxLeft1, maxLeft2))
            }
        } else if maxLeft1 > minRight2 {
            high = partition1 - 1
        } else {
            low = partition1 + 1
        }
    }

    return 0.0
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

type Solution struct{}

Go doesn't have ternary operators, so the sentinel value logic uses explicit if-statements. The max and min helper functions are defined manually since Go's standard library didn't include generic versions until recently.

TypeScript

class Solution {
  findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    if (nums1.length > nums2.length) {
      return this.findMedianSortedArrays(nums2, nums1);
    }

    const smallerLength = nums1.length;
    const largerLength = nums2.length;
    let low = 0;
    let high = smallerLength;

    while (low <= high) {
      const partition1 = Math.floor((low + high) / 2);
      const partition2 = Math.floor((smallerLength + largerLength + 1) / 2) - partition1;

      const maxLeft1 = (partition1 === 0) ? Number.NEGATIVE_INFINITY : nums1[partition1 - 1];
      const minRight1 = (partition1 === smallerLength) ? Number.POSITIVE_INFINITY : nums1[partition1];

      const maxLeft2 = (partition2 === 0) ? Number.NEGATIVE_INFINITY : nums2[partition2 - 1];
      const minRight2 = (partition2 === largerLength) ? Number.POSITIVE_INFINITY : nums2[partition2];

      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
        if ((smallerLength + largerLength) % 2 === 0) {
          return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
        } else {
          return Math.max(maxLeft1, maxLeft2);
        }
      } else if (maxLeft1 > minRight2) {
        high = partition1 - 1;
      } else {
        low = partition1 + 1;
      }
    }

    throw new Error("Input arrays are not sorted.");
  }
}

export { Solution };

The TypeScript version is structurally identical to JavaScript but adds type annotations on the parameters and return type.

Scala

class Solution {
  def findMedianSortedArrays(nums1: Array[Int], nums2: Array[Int]): Double = {
    val (smaller, larger) = if (nums1.length > nums2.length) (nums2, nums1) else (nums1, nums2)
    val smallerLength = smaller.length
    val largerLength = larger.length
    var low = 0
    var high = smallerLength
    val halfLen = (smallerLength + largerLength + 1) / 2

    while (low <= high) {
      val partition1 = (low + high) / 2
      val partition2 = halfLen - partition1

      if (partition1 < smallerLength && smaller(partition1) < larger(partition2 - 1)) {
        low = partition1 + 1
      } else if (partition1 > 0 && smaller(partition1 - 1) > larger(partition2)) {
        high = partition1 - 1
      } else {
        val maxOfLeft = if (partition1 == 0) larger(partition2 - 1)
                        else if (partition2 == 0) smaller(partition1 - 1)
                        else math.max(smaller(partition1 - 1), larger(partition2 - 1))

        if ((smallerLength + largerLength) % 2 == 1) {
          return maxOfLeft
        }

        val minOfRight = if (partition1 == smallerLength) larger(partition2)
                         else if (partition2 == largerLength) smaller(partition1)
                         else math.min(smaller(partition1), larger(partition2))

        return (maxOfLeft + minOfRight) / 2.0
      }
    }
    0.0
  }
}

The Scala version uses val for immutable bindings and pattern matching to destructure the array swap. The comparison logic is slightly restructured but achieves the same partition search.

Swift

import Foundation

class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        if nums1.count > nums2.count {
            return findMedianSortedArrays(nums2, nums1)
        }

        let smallerLength = nums1.count
        let largerLength = nums2.count
        var low = 0
        var high = smallerLength

        while low <= high {
            let partition1 = (low + high) / 2
            let partition2 = (smallerLength + largerLength + 1) / 2 - partition1

            let maxLeft1 = (partition1 == 0) ? Int.min : nums1[partition1 - 1]
            let minRight1 = (partition1 == smallerLength) ? Int.max : nums1[partition1]

            let maxLeft2 = (partition2 == 0) ? Int.min : nums2[partition2 - 1]
            let minRight2 = (partition2 == largerLength) ? Int.max : nums2[partition2]

            if maxLeft1 <= minRight2 && maxLeft2 <= minRight1 {
                if (smallerLength + largerLength) % 2 == 0 {
                    return (Double(max(maxLeft1, maxLeft2)) + Double(min(minRight1, minRight2))) / 2.0
                } else {
                    return Double(max(maxLeft1, maxLeft2))
                }
            } else if maxLeft1 > minRight2 {
                high = partition1 - 1
            } else {
                low = partition1 + 1
            }
        }

        fatalError("Input arrays are not sorted.")
    }
}

Swift uses Int.min and Int.max for sentinel values. The built-in max() and min() functions work directly with Int types.

Kotlin

class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        if (nums1.size > nums2.size) {
            return findMedianSortedArrays(nums2, nums1)
        }

        val smallerLength = nums1.size
        val largerLength = nums2.size
        var low = 0
        var high = smallerLength

        while (low <= high) {
            val partition1 = (low + high) / 2
            val partition2 = (smallerLength + largerLength + 1) / 2 - partition1

            val maxLeft1 = if (partition1 == 0) Int.MIN_VALUE else nums1[partition1 - 1]
            val minRight1 = if (partition1 == smallerLength) Int.MAX_VALUE else nums1[partition1]

            val maxLeft2 = if (partition2 == 0) Int.MIN_VALUE else nums2[partition2 - 1]
            val minRight2 = if (partition2 == largerLength) Int.MAX_VALUE else nums2[partition2]

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((smallerLength + largerLength) % 2 == 0) {
                    return (maxOf(maxLeft1, maxLeft2).toDouble() + minOf(minRight1, minRight2)) / 2
                } else {
                    return maxOf(maxLeft1, maxLeft2).toDouble()
                }
            } else if (maxLeft1 > minRight2) {
                high = partition1 - 1
            } else {
                low = partition1 + 1
            }
        }

        throw IllegalArgumentException("Input arrays are not sorted.")
    }
}

Kotlin's maxOf() and minOf() functions and its if-expressions (which return values) make the code concise while keeping the logic clear.

Ruby

class Solution
  def find_median_sorted_arrays(nums1, nums2)
    return find_median_sorted_arrays(nums2, nums1) if nums1.length > nums2.length

    smaller_length = nums1.length
    larger_length = nums2.length
    low = 0
    high = smaller_length

    while low <= high
      partition1 = (low + high) / 2
      partition2 = (smaller_length + larger_length + 1) / 2 - partition1

      max_left1 = partition1.zero? ? -Float::INFINITY : nums1[partition1 - 1]
      min_right1 = partition1 == smaller_length ? Float::INFINITY : nums1[partition1]

      max_left2 = partition2.zero? ? -Float::INFINITY : nums2[partition2 - 1]
      min_right2 = partition2 == larger_length ? Float::INFINITY : nums2[partition2]

      if max_left1 <= min_right2 && max_left2 <= min_right1
        if (smaller_length + larger_length).even?
          return ([max_left1, max_left2].max + [min_right1, min_right2].min) / 2.0
        else
          return [max_left1, max_left2].max.to_f
        end
      elsif max_left1 > min_right2
        high = partition1 - 1
      else
        low = partition1 + 1
      end
    end

    raise ArgumentError, 'Input arrays are not sorted.'
  end
end

Ruby uses Float::INFINITY and -Float::INFINITY for sentinel values. The .even? method provides a clean check for the total length parity.

Rust

pub struct Solution;

impl Solution {
    pub fn find_median_sorted_arrays(&self, nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        if nums1.len() > nums2.len() {
            return self.find_median_sorted_arrays(nums2, nums1);
        }

        let smaller_length = nums1.len();
        let larger_length = nums2.len();
        let mut low = 0;
        let mut high = smaller_length;

        while low <= high {
            let partition1 = (low + high) / 2;
            let partition2 = (smaller_length + larger_length + 1) / 2 - partition1;

            let max_left1 = if partition1 == 0 { i32::MIN } else { nums1[partition1 - 1] };
            let min_right1 = if partition1 == smaller_length { i32::MAX } else { nums1[partition1] };

            let max_left2 = if partition2 == 0 { i32::MIN } else { nums2[partition2 - 1] };
            let min_right2 = if partition2 == larger_length { i32::MAX } else { nums2[partition2] };

            if max_left1 <= min_right2 && max_left2 <= min_right1 {
                if (smaller_length + larger_length) % 2 == 0 {
                    return (max_left1.max(max_left2) as f64 + min_right1.min(min_right2) as f64) / 2.0;
                } else {
                    return max_left1.max(max_left2) as f64;
                }
            } else if max_left1 > min_right2 {
                high = partition1 - 1;
            } else {
                low = partition1 + 1;
            }
        }

        panic!("Input arrays are not sorted.");
    }
}

Rust uses i32::MIN and i32::MAX for sentinels. The .max() and .min() methods are available directly on i32 values, and as f64 handles the cast to floating-point.

C#

using System;

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.Length > nums2.Length) {
            return FindMedianSortedArrays(nums2, nums1);
        }

        int smallerLength = nums1.Length;
        int largerLength = nums2.Length;
        int low = 0;
        int high = smallerLength;

        while (low <= high) {
            int partition1 = (low + high) / 2;
            int partition2 = (smallerLength + largerLength + 1) / 2 - partition1;

            int maxLeft1 = (partition1 == 0) ? int.MinValue : nums1[partition1 - 1];
            int minRight1 = (partition1 == smallerLength) ? int.MaxValue : nums1[partition1];

            int maxLeft2 = (partition2 == 0) ? int.MinValue : nums2[partition2 - 1];
            int minRight2 = (partition2 == largerLength) ? int.MaxValue : nums2[partition2];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((smallerLength + largerLength) % 2 == 0) {
                    return ((double)Math.Max(maxLeft1, maxLeft2) + Math.Min(minRight1, minRight2)) / 2;
                } else {
                    return (double)Math.Max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                high = partition1 - 1;
            } else {
                low = partition1 + 1;
            }
        }

        throw new ArgumentException("Input arrays are not sorted.");
    }
}

C# uses int.MinValue and int.MaxValue for sentinels. The Math.Max() and Math.Min() methods from the System namespace handle the boundary comparisons.

Dart

class Solution {
  double findMedianSortedArrays(List<int> nums1, List<int> nums2) {
    if (nums1.length > nums2.length) {
      return findMedianSortedArrays(nums2, nums1);
    }

    int smallerLength = nums1.length;
    int largerLength = nums2.length;
    int low = 0;
    int high = smallerLength;

    while (low <= high) {
      int partition1 = (low + high) ~/ 2;
      int partition2 = (smallerLength + largerLength + 1) ~/ 2 - partition1;

      int maxLeft1 = (partition1 == 0) ? (-1 << 31) : nums1[partition1 - 1];
      int minRight1 = (partition1 == smallerLength) ? ((1 << 31) - 1) : nums1[partition1];

      int maxLeft2 = (partition2 == 0) ? (-1 << 31) : nums2[partition2 - 1];
      int minRight2 = (partition2 == largerLength) ? ((1 << 31) - 1) : nums2[partition2];

      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
        if ((smallerLength + largerLength) % 2 == 0) {
          int maxLeft = maxLeft1 > maxLeft2 ? maxLeft1 : maxLeft2;
          int minRight = minRight1 < minRight2 ? minRight1 : minRight2;
          return (maxLeft + minRight) / 2;
        } else {
          return (maxLeft1 > maxLeft2 ? maxLeft1 : maxLeft2).toDouble();
        }
      } else if (maxLeft1 > minRight2) {
        high = partition1 - 1;
      } else {
        low = partition1 + 1;
      }
    }

    throw ArgumentError("Input arrays are not sorted.");
  }
}

Dart uses ~/ for integer division and bit shifting (-1 << 31 and (1 << 31) - 1) to create sentinel values equivalent to 32-bit integer min/max.

PHP

class Solution {
    public function findMedianSortedArrays(array $nums1, array $nums2): float {
        if (count($nums1) > count($nums2)) {
            return $this->findMedianSortedArrays($nums2, $nums1);
        }

        $smallerLength = count($nums1);
        $largerLength = count($nums2);
        $low = 0;
        $high = $smallerLength;

        while ($low <= $high) {
            $partition1 = intdiv($low + $high, 2);
            $partition2 = intdiv($smallerLength + $largerLength + 1, 2) - $partition1;

            $maxLeft1 = ($partition1 === 0) ? PHP_INT_MIN : $nums1[$partition1 - 1];
            $minRight1 = ($partition1 === $smallerLength) ? PHP_INT_MAX : $nums1[$partition1];

            $maxLeft2 = ($partition2 === 0) ? PHP_INT_MIN : $nums2[$partition2 - 1];
            $minRight2 = ($partition2 === $largerLength) ? PHP_INT_MAX : $nums2[$partition2];

            if ($maxLeft1 <= $minRight2 && $maxLeft2 <= $minRight1) {
                if (($smallerLength + $largerLength) % 2 === 0) {
                    return (max($maxLeft1, $maxLeft2) + min($minRight1, $minRight2)) / 2.0;
                } else {
                    return (float)max($maxLeft1, $maxLeft2);
                }
            } elseif ($maxLeft1 > $minRight2) {
                $high = $partition1 - 1;
            } else {
                $low = $partition1 + 1;
            }
        }

        throw new \InvalidArgumentException("Input arrays are not sorted.");
    }
}

PHP uses PHP_INT_MIN and PHP_INT_MAX for sentinels, and intdiv() for integer division. The max() and min() built-in functions handle the boundary comparisons.

Practice Makes Perfect

Once you're comfortable with this problem, try these related challenges to reinforce the partition-based binary search pattern:

• Kth Element of Two Sorted Arrays (generalization beyond the median)
• Merge Two Sorted Arrays (the brute-force version, good for contrast)
• Search in Rotated Sorted Array (another modified binary search)
• Find K Closest Elements (binary search on a sorted array)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. If this problem gave you trouble, Firecode's spaced repetition system will bring it back at the right time until the partition logic becomes second nature.