Median of Two Sorted Arrays in Java | Binary Search Partition | Java Interview Prep: Advanced #05

Code & Test Automation |    / @codetestautomation   Learn how to find the median of two sorted arrays in Java in logarithmic time with a binary-searched partition, a classic hard coding interview question! In this lesson we cover the contract (ascending int arrays, at least one nonempty, no merging), a picture of cutting both arrays so the left halves hold half the values, the simple merge-walk idea that costs O(m + n), the plan from the guide, the Java code line by line, a full dry run of [1, 3] and [2] (answer 2.0), the even case [1, 2] and [3, 4] (answer 2.5), edge cases such as one empty array and extreme int values, complexity, and the follow-up: why the cut in the longer array always stays in range. Episode 5 of 20 in Java Interview Prep: Advanced (advanced windows, monotonic structures, linked lists, trees, tries, dynamic programming, weighted graphs and backtracking). CHAPTERS 0:00 Introduction 0:51 The problem 1:39 Intuition 2:31 The simple idea 3:12 The plan 3:44 The Java code 4:54 Dry run 6:19 Even total 7:08 Edge cases & tests 8:05 Complexity 8:33 Interview follow-up 9:14 Recap 9:45 Subscribe THE SOLUTION (Java) static double medianOfSortedArrays(int[] a, int[] b) { if (a.length › b.length) return medianOfSortedArrays(b, a); int m = a.length, n = b.length; if (m == 0 && n == 0) throw new IllegalArgumentException(); int half = (int) (((long) m + n + 1) / 2); int lo = 0, hi = m; while (lo ‹= hi) { int i = lo + (hi - lo) / 2, j = half - i; int al = i == 0 ? Integer.MIN_VALUE : a[i - 1]; int ar = i == m ? Integer.MAX_VALUE : a[i]; int bl = j == 0 ? Integer.MIN_VALUE : b[j - 1]; int br = j == n ? Integer.MAX_VALUE : b[j]; if (al ‹= br && bl ‹= ar) { if ((((long) m + n) & 1) == 1) return Math.max(al, bl); return ((long) Math.max(al, bl) + Math.min(ar, br)) / 2.0; } if (al › br) hi = i - 1; else lo = i + 1; } throw new IllegalArgumentException("Inputs must be sorted"); } Example: medianOfSortedArrays([1,3], [2]) =› 2.0; ([1,2], [3,4]) =› 2.5 Complexity: O(log(min(m,n)+2)) search time; O(1) auxiliary space. Practice tip: type it, run it, then explain it out loud: the invariant, the complexity and the edge cases. Next episode: #06 Merge K sorted linked lists. #Java #CodingInterview #DSA #CodeAndTestAutomation Subscribe to Code & Test Automation for more Java interview prep:    / @codetestautomation