Median of Two Sorted Arrays

Animated walkthrough

Step through the algorithm visually — use Play or the step buttons (inspired by AlgoMaster / visualgo).

Step 1 / 1

Bloomberg interview context: Median of Two Sorted Arrays is a Hard Binary Search problem — Binary search on index or on the answer (binary search on value).

Use the animation above to step through each move before writing code.

Pattern: Binary Search

Read from stdin, write to stdout. Classic interview problem #4.

Problem

Median of Two Sorted Arrays — Bloomberg interview prep · Binary Search

Classic interview problem #4.

Input (stdin)

Line 1: nums1\nLine 2: nums2

Output (stdout)

Median (decimal)

Your program must read from stdin and write the answer to stdout (no extra debug text).

Examples

Sample

Input

1 3
2

Output

2.0

Hints

Input format: Line 1: nums1\nLine 2: nums2
DSA Interview 150 — Binary Search
Problem #4
Frequently asked at Bloomberg
Binary Search

Your solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static int[] Ria(string line = null)
    {
        line ??= Console.ReadLine();
        if (string.IsNullOrWhiteSpace(line)) return Array.Empty<int>();
        return line.Trim().Split(new[] { ' ', ',', '\t' }, StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse).ToArray();
    }
    static string[] Rsa()
    {
        int n = int.Parse(Console.ReadLine());
        var arr = new string[n];
        for (int i = 0; i < n; i++) arr[i] = Console.ReadLine();
        return arr;
    }
    static void W(params object[] parts) => Console.WriteLine(string.Join(" ", parts));
    static void Wb(bool v) => Console.WriteLine(v ? "true" : "false");
    static void Wi(int v) => Console.WriteLine(v);
    static void Ws(string v) => Console.WriteLine(v);

static void Main()
    {
        // Read from stdin (see problem statement for format)
        // Line 1: nums1\nLine 2: nums2

}
}

Ready — edit the code above and click Run or Submit.

Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static int[] Ria(string line = null)
    {
        line ??= Console.ReadLine();
        if (string.IsNullOrWhiteSpace(line)) return Array.Empty<int>();
        return line.Trim().Split(new[] { ' ', ',', '\t' }, StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse).ToArray();
    }
    static string[] Rsa()
    {
        int n = int.Parse(Console.ReadLine());
        var arr = new string[n];
        for (int i = 0; i < n; i++) arr[i] = Console.ReadLine();
        return arr;
    }
    static void W(params object[] parts) => Console.WriteLine(string.Join(" ", parts));
    static void Wb(bool v) => Console.WriteLine(v ? "true" : "false");
    static void Wi(int v) => Console.WriteLine(v);
    static void Ws(string v) => Console.WriteLine(v);

    static void Main()
    {
var a = Ria();
var b = Ria(Console.ReadLine());
int m = a.Length, n = b.Length;
if (m > n) { var tmp = a; a = b; b = tmp; m = b.Length; n = a.Length; }
int lo = 0, hi = m;
double median = 0;
while (lo <= hi) {
    int i = lo + (hi - lo) / 2, j = (m + n + 1) / 2 - i;
    int maxLeftA = i == 0 ? int.MinValue : a[i - 1];
    int minRightA = i == m ? int.MaxValue : a[i];
    int maxLeftB = j == 0 ? int.MinValue : b[j - 1];
    int minRightB = j == n ? int.MaxValue : b[j];
    if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
        median = (m + n) % 2 == 1 ? Math.Max(maxLeftA, maxLeftB)
            : (Math.Max(maxLeftA, maxLeftB) + Math.Min(minRightA, minRightB)) / 2.0;
        break;
    }
    if (maxLeftA > minRightB) hi = i - 1; else lo = i + 1;
}
Console.WriteLine(median.ToString("0.0##", System.Globalization.CultureInfo.InvariantCulture));
    }
}

Try solving on your own first, then reveal the official answer.

Animated walkthrough

Problem

Examples

Your solution

Solution

Discussion