DSA-068 · Balance a two-array partition with four boundary values

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.0
Search 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.5
Partition [1,2] | [] on the left and [] | [3,4] on the right; middle values are 2 and 3.
Input: a=[], b=[MIN,MAX]
Output: −0.5
The 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.0
Adding 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.

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.

Median — cuts and four bordering values

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.

State after this step
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.

Median — cuts and four bordering values

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.

State after this step
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.

Median — cuts and four bordering values

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.

State after this step
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.

Median — cuts and four bordering values

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.

State after this step
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.0
One empty input.
Input: [1,3],[2]
Output: 2.0
Odd total with shorter-array role swap.
Input: [1,2],[3,4]
Output: 2.5
Even cross-array middle values.
Input: [MIN],[MAX]
Output: −0.5
Widened arithmetic and exact half.
Input: [],[]
Output: IllegalArgumentException
No defined median.
Input: [MAX],[MAX]
Output: MAX as double
No 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.

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.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 116/20,000 characters

Self-review

I justify both the left size and the admissible second cut.I prove cut movement rather than memorizing the four comparisons.I handle empty sides, duplicates, and int extremes without sentinel or averaging errors.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Binary search: candidate intervals and monotone feasibility

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.