DSA-068 · FOCUSED PRACTICE
Median of Two Sorted Arrays
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 10290 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the numeric median of two nondecreasing int arrays without merging them in the optimized method. Search a partition in the shorter array and preserve both inputs.
- a and b are nonnull, sorted nondecreasing arrays of at most 100,000 ints each; duplicates and all int extremes are allowed. Sortedness is an unchecked precondition to retain sublinear time.
- At least one array must be nonempty. Both empty throws IllegalArgumentException; a null array throws NullPointerException. For odd total length return the middle value; for even total return the arithmetic mean of the two middle values as double.
- Both methods are read-only, including when the same array object is passed twice. Widen total length and middle-value addition before arithmetic; every possible median is an exactly representable integer or half-integer in double. Missing partition boundaries use long sentinels outside the int value domain.
Examples
Input:
a=[1,3], b=[2]
Output:2.0Search the shorter [2] array. A valid left partition contains ceil(3/2)=2 values; its maximum is the odd median.
Input:
a=[1,2], b=[3,4]
Output:2.5Partition [1,2] | [] on the left and [] | [3,4] on the right; middle values are 2 and 3.
Input:
a=[], b=[MIN,MAX]
Output:−0.5The empty shorter array has one possible cut. Widened (MIN+MAX)/2.0 is −0.5.
Input:
a=[MAX], b=[MAX]
Output:2,147,483,647.0Adding the middle values as int would overflow; long addition preserves the answer.
Before you start
- Binary-search movement proofs
- Sorted prefixes and rank partitions
- Safe widening and conceptual missing boundaries
Recognize the structure
The median is defined by rank, not by averaging each array’s median. A valid partition must place ceil(total/2) values on the left and keep every left value <= every right value. Sortedness reduces that global ordering condition to two cross-boundary comparisons.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 116/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
A median split puts ceil(total/2) values on the left, regardless of which array supplies them.
Hint 2
Choose i from the shorter array; the other cut j is fixed by the required left count.
Hint 3
Check aLeft<=bRight and bLeft<=aRight; move i away from a boundary that is too large, then read the middle value(s).
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Merge only through the middle rank
Walk two sorted arrays with cursors, repeatedly consume the smaller next value, and retain only previous/current until the combined middle rank is reached. For [1,2] and [3,4], consumed values through index 2 are 1,2,3, so the even median is (2+3)/2=2.5. This O(n+m)-time baseline uses O(1) auxiliary state rather than allocating a full merge; tests independently sort a concatenated union as the oracle.
Improve the baseline
Search the shorter array’s cut
Swap array roles once if needed so m<=n. A cut i in [0,m] puts i elements of A on the left, forcing j=ceil((m+n)/2)−i elements of B onto the left. For every such i, j stays in [0,n].
Check four bordering values
aLeft=A[i−1], aRight=A[i], bLeft=B[j−1], bRight=B[j], with conceptual −infinity/+infinity for missing sides. Internal array order is already correct; only aLeft<=bRight and bLeft<=aRight remain to check.
Move a proven impossible cut side
If aLeft>bRight, too many A values are on the left: decrease i. If bLeft>aRight, too few A values are on the left: increase i. At a valid cut, odd median is max(left values), and even median averages max(left) and min(right).
Why it is correct
Partition sizes are valid
With m<=n and leftCount=ceil((m+n)/2), m<=leftCount<=n, so j=leftCount−i belongs to [0,n] for every i in [0,m]. The shorter-array search therefore never creates an invalid B cut.
Directional elimination
If A[i−1]>B[j], increasing i only increases A’s left boundary and decreases j, which cannot increase B’s right boundary; all cuts at or to the right are invalid. Conversely B[j−1]>A[i] rules out all cuts at or to the left. Thus binary search retains a valid cut obtainable by splitting a conceptual sorted merge at leftCount.
Median characterization
At a cut satisfying both cross inequalities, all left-partition values are <= all right-partition values and partition sizes differ by at most one. The largest left value is the odd middle; with an even total the smallest right value is the next middle. These boundaries are real int values in the applicable cases, so long-sentinel values never enter the returned arithmetic.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.Objects;
public final class Solution {
public static double median(int[] a, int[] b) {
Objects.requireNonNull(a, "a");
Objects.requireNonNull(b, "b");
if (a.length > b.length) return median(b, a);
long total = (long) a.length + b.length;
if (total == 0) throw new IllegalArgumentException("both arrays empty");
int leftCount = (int) ((total + 1) / 2);
int low = 0, high = a.length;
while (low <= high) {
int i = low + (high - low) / 2;
int j = leftCount - i;
long aLeft = i == 0 ? Long.MIN_VALUE : a[i - 1];
long aRight = i == a.length ? Long.MAX_VALUE : a[i];
long bLeft = j == 0 ? Long.MIN_VALUE : b[j - 1];
long bRight = j == b.length ? Long.MAX_VALUE : b[j];
if (aLeft > bRight) high = i - 1;
else if (bLeft > aRight) low = i + 1;
else {
long lower = Math.max(aLeft, bLeft);
if (total % 2 == 1) return lower;
long upper = Math.min(aRight, bRight);
return (lower + upper) / 2.0;
}
}
throw new IllegalArgumentException("sorted-input precondition violated");
}
public static double baseline(int[] a, int[] b) {
Objects.requireNonNull(a, "a");
Objects.requireNonNull(b, "b");
long total = (long) a.length + b.length;
if (total == 0) throw new IllegalArgumentException("both arrays empty");
int i = 0, j = 0;
long previous = 0, current = 0;
for (long k = 0; k <= total / 2; k++) {
previous = current;
current = j == b.length || (i < a.length && a[i] <= b[j]) ? a[i++] : b[j++];
}
return total % 2 == 1 ? current : (previous + current) / 2.0;
}
}
Read the meaningful blocks
One bounded role swap
The method calls itself at most once to make A shorter; this is constant call-stack overhead, not depth proportional to input length.
Absent boundaries outside int range
Long.MIN_VALUE/MAX_VALUE serve as mathematical missing endpoints because actual data are ints. Walkthroughs display them as −infinity/+infinity labels rather than unsafe JavaScript long numbers.
Widened median arithmetic
Total length is long before addition. Both middle values are held as long before their sum is divided by 2.0, preventing int overflow and integer truncation.
Complexity
Partition search uses O(log(min(n,m)+1)) probes and O(1) auxiliary workspace, with one possible constant-depth role swap. If one input is empty there is only one cut, so lookup is constant-time under the sorted-input precondition.
The partial-merge baseline takes O(n+m) time and O(1) auxiliary space. A full validation or concatenation/sort would add linear or larger preprocessing work; the implementation does not hide that work in the logarithmic claim.
Exact-state walkthroughs
Reveal normal and boundary traces
Odd total searches the shorter array
Input: {"a":[1,3],"b":[2]} · Median value: 2
Step 1 of 4: Choose the shorter A role and search its cut positions.
A contributes i left-side values and B contributes j=leftCount−i. Every candidate i gives an in-range j.
Candidate A cuts: [0, 1]. Left partition needs 2 values. A below is the original B (the shorter input); B below is the original A.
A cut: not probed
- index 02not partitioned
B cut: not probed
- index 01not partitioned
- index 13not partitioned
Probe one shorter-array cut; the other cut is fixed by the left size. Inputs are never changed. The cut shown is the last probe and may lie outside the newly retained cut interval.
| Variable | Value |
|---|---|
| a | [2] |
| b | [1,3] |
| swapped | true |
| total | 3 |
| leftCount | 2 |
| low | 0 |
| high | 1 |
| phase | "partition" |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 public static double median(int[] a, int[] b) { 5 Objects.requireNonNull(a, "a"); 6 Objects.requireNonNull(b, "b"); 7 if (a.length > b.length) return median(b, a); 8 long total = (long) a.length + b.length; 9 if (total == 0) throw new IllegalArgumentException("both arrays empty"); 10 int leftCount = (int) ((total + 1) / 2); 11 int low = 0, high = a.length; 12 while (low <= high) { 13 int i = low + (high - low) / 2; 14 int j = leftCount - i; 15 long aLeft = i == 0 ? Long.MIN_VALUE : a[i - 1]; 16 long aRight = i == a.length ? Long.MAX_VALUE : a[i]; 17 long bLeft = j == 0 ? Long.MIN_VALUE : b[j - 1]; 18 long bRight = j == b.length ? Long.MAX_VALUE : b[j]; 19 if (aLeft > bRight) high = i - 1; 20 else if (bLeft > aRight) low = i + 1; 21 else { 22 long lower = Math.max(aLeft, bLeft); 23 if (total % 2 == 1) return lower; 24 long upper = Math.min(aRight, bRight); 25 return (lower + upper) / 2.0; 26 } 27 } 28 throw new IllegalArgumentException("sorted-input precondition violated"); 29 } 30 public static double baseline(int[] a, int[] b) { 31 Objects.requireNonNull(a, "a"); 32 Objects.requireNonNull(b, "b"); 33 long total = (long) a.length + b.length; 34 if (total == 0) throw new IllegalArgumentException("both arrays empty"); 35 int i = 0, j = 0; 36 long previous = 0, current = 0; 37 for (long k = 0; k <= total / 2; k++) { 38 previous = current; 39 current = j == b.length || (i < a.length && a[i] <= b[j]) ? a[i++] : b[j++]; 40 } 41 return total % 2 == 1 ? current : (previous + current) / 2.0; 42 } 43 } 44
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Choose the shorter A role and search its cut positions.
A contributes i left-side values and B contributes j=leftCount−i. Every candidate i gives an in-range j.
- a
[2]- b
[1,3]- swapped
true- total
3- leftCount
2- low
0- high
1- phase
"partition"
- B left boundary is too large; move the A cut right.
All cuts at or to the left leave too few A values on the left; retain larger A cuts.
- a
[2]- b
[1,3]- swapped
true- total
3- leftCount
2- low
1- high
1- phase
"partition"- before
[0,1]- i
0- j
2- boundaries
{"aLeft":"−infinity","aRight":2,"bLeft":3,"bRight":"+infinity"}- move
"right"
- Both cross inequalities hold; read the real middle boundary values.
All left values are <= all right values and rank sizes are balanced. Missing-boundary labels never enter the returned arithmetic.
- a
[2]- b
[1,3]- swapped
true- total
3- leftCount
2- low
1- high
1- phase
"partition"- before
[1,1]- i
1- j
1- boundaries
{"aLeft":2,"aRight":"+infinity","bLeft":1,"bRight":3}- move
"valid"- lower
2- upper
null
- Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
- result
2
Move the A cut right for an even median
Input: {"a":[1,2],"b":[3,4]} · Median value: 2.5
Step 1 of 4: Choose the shorter A role and search its cut positions.
A contributes i left-side values and B contributes j=leftCount−i. Every candidate i gives an in-range j.
Candidate A cuts: [0, 2]. Left partition needs 2 values. A below is no longer than B; original roles are retained.
A cut: not probed
- index 01not partitioned
- index 12not partitioned
B cut: not probed
- index 03not partitioned
- index 14not partitioned
Probe one shorter-array cut; the other cut is fixed by the left size. Inputs are never changed. The cut shown is the last probe and may lie outside the newly retained cut interval.
| Variable | Value |
|---|---|
| a | [1,2] |
| b | [3,4] |
| swapped | false |
| total | 4 |
| leftCount | 2 |
| low | 0 |
| high | 2 |
| phase | "partition" |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 public static double median(int[] a, int[] b) { 5 Objects.requireNonNull(a, "a"); 6 Objects.requireNonNull(b, "b"); 7 if (a.length > b.length) return median(b, a); 8 long total = (long) a.length + b.length; 9 if (total == 0) throw new IllegalArgumentException("both arrays empty"); 10 int leftCount = (int) ((total + 1) / 2); 11 int low = 0, high = a.length; 12 while (low <= high) { 13 int i = low + (high - low) / 2; 14 int j = leftCount - i; 15 long aLeft = i == 0 ? Long.MIN_VALUE : a[i - 1]; 16 long aRight = i == a.length ? Long.MAX_VALUE : a[i]; 17 long bLeft = j == 0 ? Long.MIN_VALUE : b[j - 1]; 18 long bRight = j == b.length ? Long.MAX_VALUE : b[j]; 19 if (aLeft > bRight) high = i - 1; 20 else if (bLeft > aRight) low = i + 1; 21 else { 22 long lower = Math.max(aLeft, bLeft); 23 if (total % 2 == 1) return lower; 24 long upper = Math.min(aRight, bRight); 25 return (lower + upper) / 2.0; 26 } 27 } 28 throw new IllegalArgumentException("sorted-input precondition violated"); 29 } 30 public static double baseline(int[] a, int[] b) { 31 Objects.requireNonNull(a, "a"); 32 Objects.requireNonNull(b, "b"); 33 long total = (long) a.length + b.length; 34 if (total == 0) throw new IllegalArgumentException("both arrays empty"); 35 int i = 0, j = 0; 36 long previous = 0, current = 0; 37 for (long k = 0; k <= total / 2; k++) { 38 previous = current; 39 current = j == b.length || (i < a.length && a[i] <= b[j]) ? a[i++] : b[j++]; 40 } 41 return total % 2 == 1 ? current : (previous + current) / 2.0; 42 } 43 } 44
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Choose the shorter A role and search its cut positions.
A contributes i left-side values and B contributes j=leftCount−i. Every candidate i gives an in-range j.
- a
[1,2]- b
[3,4]- swapped
false- total
4- leftCount
2- low
0- high
2- phase
"partition"
- B left boundary is too large; move the A cut right.
All cuts at or to the left leave too few A values on the left; retain larger A cuts.
- a
[1,2]- b
[3,4]- swapped
false- total
4- leftCount
2- low
2- high
2- phase
"partition"- before
[0,2]- i
1- j
1- boundaries
{"aLeft":1,"aRight":2,"bLeft":3,"bRight":4}- move
"right"
- Both cross inequalities hold; read the real middle boundary values.
All left values are <= all right values and rank sizes are balanced. Missing-boundary labels never enter the returned arithmetic.
- a
[1,2]- b
[3,4]- swapped
false- total
4- leftCount
2- low
2- high
2- phase
"partition"- before
[2,2]- i
2- j
0- boundaries
{"aLeft":2,"aRight":"+infinity","bLeft":"−infinity","bRight":3}- move
"valid"- lower
2- upper
3
- Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
- result
2.5
Move the A cut left
Input: {"a":[3,4],"b":[1,2]} · Median value: 2.5
Step 1 of 4: Choose the shorter A role and search its cut positions.
A contributes i left-side values and B contributes j=leftCount−i. Every candidate i gives an in-range j.
Candidate A cuts: [0, 2]. Left partition needs 2 values. A below is no longer than B; original roles are retained.
A cut: not probed
- index 03not partitioned
- index 14not partitioned
B cut: not probed
- index 01not partitioned
- index 12not partitioned
Probe one shorter-array cut; the other cut is fixed by the left size. Inputs are never changed. The cut shown is the last probe and may lie outside the newly retained cut interval.
| Variable | Value |
|---|---|
| a | [3,4] |
| b | [1,2] |
| swapped | false |
| total | 4 |
| leftCount | 2 |
| low | 0 |
| high | 2 |
| phase | "partition" |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 public static double median(int[] a, int[] b) { 5 Objects.requireNonNull(a, "a"); 6 Objects.requireNonNull(b, "b"); 7 if (a.length > b.length) return median(b, a); 8 long total = (long) a.length + b.length; 9 if (total == 0) throw new IllegalArgumentException("both arrays empty"); 10 int leftCount = (int) ((total + 1) / 2); 11 int low = 0, high = a.length; 12 while (low <= high) { 13 int i = low + (high - low) / 2; 14 int j = leftCount - i; 15 long aLeft = i == 0 ? Long.MIN_VALUE : a[i - 1]; 16 long aRight = i == a.length ? Long.MAX_VALUE : a[i]; 17 long bLeft = j == 0 ? Long.MIN_VALUE : b[j - 1]; 18 long bRight = j == b.length ? Long.MAX_VALUE : b[j]; 19 if (aLeft > bRight) high = i - 1; 20 else if (bLeft > aRight) low = i + 1; 21 else { 22 long lower = Math.max(aLeft, bLeft); 23 if (total % 2 == 1) return lower; 24 long upper = Math.min(aRight, bRight); 25 return (lower + upper) / 2.0; 26 } 27 } 28 throw new IllegalArgumentException("sorted-input precondition violated"); 29 } 30 public static double baseline(int[] a, int[] b) { 31 Objects.requireNonNull(a, "a"); 32 Objects.requireNonNull(b, "b"); 33 long total = (long) a.length + b.length; 34 if (total == 0) throw new IllegalArgumentException("both arrays empty"); 35 int i = 0, j = 0; 36 long previous = 0, current = 0; 37 for (long k = 0; k <= total / 2; k++) { 38 previous = current; 39 current = j == b.length || (i < a.length && a[i] <= b[j]) ? a[i++] : b[j++]; 40 } 41 return total % 2 == 1 ? current : (previous + current) / 2.0; 42 } 43 } 44
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Choose the shorter A role and search its cut positions.
A contributes i left-side values and B contributes j=leftCount−i. Every candidate i gives an in-range j.
- a
[3,4]- b
[1,2]- swapped
false- total
4- leftCount
2- low
0- high
2- phase
"partition"
- A left boundary is too large; move its cut left.
All cuts at or to the right keep A left too high and B right no higher, so those cuts are impossible.
- a
[3,4]- b
[1,2]- swapped
false- total
4- leftCount
2- low
0- high
0- phase
"partition"- before
[0,2]- i
1- j
1- boundaries
{"aLeft":3,"aRight":4,"bLeft":1,"bRight":2}- move
"left"
- Both cross inequalities hold; read the real middle boundary values.
All left values are <= all right values and rank sizes are balanced. Missing-boundary labels never enter the returned arithmetic.
- a
[3,4]- b
[1,2]- swapped
false- total
4- leftCount
2- low
0- high
0- phase
"partition"- before
[0,0]- i
0- j
2- boundaries
{"aLeft":"−infinity","aRight":3,"bLeft":2,"bRight":"+infinity"}- move
"valid"- lower
2- upper
3
- Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
- result
2.5
Empty shorter side and an exact negative half
Input: {"a":[],"b":[-2147483648,2147483647]} · Median value: -0.5
Step 1 of 3: Choose the shorter A role and search its cut positions.
A contributes i left-side values and B contributes j=leftCount−i. Every candidate i gives an in-range j.
Candidate A cuts: [0, 0]. Left partition needs 1 values. A below is no longer than B; original roles are retained.
A cut: not probed
Empty array — cut zero has two conceptual missing boundaries.
B cut: not probed
- index 0-2147483648not partitioned
- index 12147483647not partitioned
Probe one shorter-array cut; the other cut is fixed by the left size. Inputs are never changed. The cut shown is the last probe and may lie outside the newly retained cut interval.
| Variable | Value |
|---|---|
| a | [] |
| b | [-2147483648,2147483647] |
| swapped | false |
| total | 2 |
| leftCount | 1 |
| low | 0 |
| high | 0 |
| phase | "partition" |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 public static double median(int[] a, int[] b) { 5 Objects.requireNonNull(a, "a"); 6 Objects.requireNonNull(b, "b"); 7 if (a.length > b.length) return median(b, a); 8 long total = (long) a.length + b.length; 9 if (total == 0) throw new IllegalArgumentException("both arrays empty"); 10 int leftCount = (int) ((total + 1) / 2); 11 int low = 0, high = a.length; 12 while (low <= high) { 13 int i = low + (high - low) / 2; 14 int j = leftCount - i; 15 long aLeft = i == 0 ? Long.MIN_VALUE : a[i - 1]; 16 long aRight = i == a.length ? Long.MAX_VALUE : a[i]; 17 long bLeft = j == 0 ? Long.MIN_VALUE : b[j - 1]; 18 long bRight = j == b.length ? Long.MAX_VALUE : b[j]; 19 if (aLeft > bRight) high = i - 1; 20 else if (bLeft > aRight) low = i + 1; 21 else { 22 long lower = Math.max(aLeft, bLeft); 23 if (total % 2 == 1) return lower; 24 long upper = Math.min(aRight, bRight); 25 return (lower + upper) / 2.0; 26 } 27 } 28 throw new IllegalArgumentException("sorted-input precondition violated"); 29 } 30 public static double baseline(int[] a, int[] b) { 31 Objects.requireNonNull(a, "a"); 32 Objects.requireNonNull(b, "b"); 33 long total = (long) a.length + b.length; 34 if (total == 0) throw new IllegalArgumentException("both arrays empty"); 35 int i = 0, j = 0; 36 long previous = 0, current = 0; 37 for (long k = 0; k <= total / 2; k++) { 38 previous = current; 39 current = j == b.length || (i < a.length && a[i] <= b[j]) ? a[i++] : b[j++]; 40 } 41 return total % 2 == 1 ? current : (previous + current) / 2.0; 42 } 43 } 44
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Choose the shorter A role and search its cut positions.
A contributes i left-side values and B contributes j=leftCount−i. Every candidate i gives an in-range j.
- a
[]- b
[-2147483648,2147483647]- swapped
false- total
2- leftCount
1- low
0- high
0- phase
"partition"
- Both cross inequalities hold; read the real middle boundary values.
All left values are <= all right values and rank sizes are balanced. Missing-boundary labels never enter the returned arithmetic.
- a
[]- b
[-2147483648,2147483647]- swapped
false- total
2- leftCount
1- low
0- high
0- phase
"partition"- before
[0,0]- i
0- j
1- boundaries
{"aLeft":"−infinity","aRight":"+infinity","bLeft":-2147483648,"bRight":2147483647}- move
"valid"- lower
-2147483648- upper
2147483647
- Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
- result
-0.5
Test the contract
Input:
[],[5]
Output:5.0One empty input.
Input:
[1,3],[2]
Output:2.0Odd total with shorter-array role swap.
Input:
[1,2],[3,4]
Output:2.5Even cross-array middle values.
Input:
[MIN],[MAX]
Output:−0.5Widened arithmetic and exact half.
Input:
[],[]
Output:IllegalArgumentExceptionNo defined median.
Input:
[MAX],[MAX]
Output:MAX as doubleNo overflowing int addition.
Common mistakes and counterexamples
Average the two individual medians
Counterexample: [1,2] and [100] have median 2, not (1.5+100)/2.
Balance combined ranks through a shared partition size.
Search the longer array without bounding the other cut
Counterexample: j can leave [0,n] when an arbitrary long-array cut is used.
Search the shorter array or derive explicit admissible cut bounds.
Move the cut in the wrong direction
Counterexample: aLeft>bRight means the A left side already contains too many large elements.
Decrease i; when bLeft>aRight, increase i.
Add middle values as int
Counterexample: MAX+MAX overflows before division even if the destination is double.
Widen operands before addition and divide by 2.0.
Treat duplicate partition boundaries as invalid
Counterexample: Equal aLeft/bRight values satisfy sorted order.
Use <= for validity; duplicates can yield several valid cuts with the same median.
Follow-ups
Find the kth smallest value of two sorted arrays.
Choose leftCount=k and constrain i to max(0,k−n)..min(k,m), then apply the same cross-boundary conditions. Median is a special choice of rank; other ranks need these explicit admissible bounds.
Data arrive as streams.
Random-access partition search no longer applies. Two heaps maintain a streaming median with different update/query and memory costs; a one-shot merged traversal is another option when both streams are already sorted.
Validate sortedness before every query.
A full scan takes O(n+m) and dominates logarithmic partition search. An immutable validated snapshot can pay construction cost once; report construction and query costs separately.