import Mathlib /-! # Median Of Two Sorted Arrays Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). ## Constraints - nums1.length == m - nums2.length == n - 0 <= m <= 1000 - 0 <= n <= 1000 - 1 <= m + n <= 2000 - -10^6 <= nums1[i], nums2[i] <= 10^6 ## Provided examples - `nums1 = [1, 3], nums2 = [2]` → `2.0` - `nums1 = [1, 2], nums2 = [3, 4]` → `2.5` - `nums1 = [2], nums2 = []` → `2.0` ## Synthesized negative examples - invalid input: `nums1 = [], nums2 = []` ([structural] a predicate that admits 1 <= m + n <= 2000. both arrays empty; each length is legal but m+n is zero) - invalid input: `nums1 = [0, 1000001], nums2 = [0]` ([structural] a predicate that admits -10^6 <= nums1[i], nums2[i] <= 10^6. last nums1 element one past upper bound; first-element-only check misses it) - invalid input: `nums1 = [-1000001, 0], nums2 = [0]` ([structural] a predicate that admits -10^6 <= nums1[i], nums2[i] <= 10^6. first nums1 element one below lower bound; last-element-only check misses it) - `nums1 = [1, 3], nums2 = [2]` → `2.5` is wrong ([structural] specification accepts the average of the two arrays' maximums as the answer. 2.5 is (3+2)/2, not the median of the merged arrays.) - `nums1 = [1, 2], nums2 = [3, 4]` → `2.0` is wrong ([structural] even-length median stated as lower middle element rather than the average of the two middle elements. 2 is one index left of the true median 2.5) - `nums1 = [2], nums2 = []` → `1.0` is wrong ([structural] off-by-one in median computation treats empty array as a zero element. average of 2 and 0 is 1.0) -/ namespace PMedianOfTwoSortedArrays abbrev Input := (List Int) × (List Int) abbrev Output := Rat /-! ### Specification helpers -/ /-- Maps a JSON float literal for a half-integral median to its exact rational value. -/ def floatToRat (x : Float) : Rat := let y := x * 2 (if y < 0 then -((-y).toUInt64.toNat : Rat) else (y.toUInt64.toNat : Rat)) / 2 /-- The number of elements belonging to the lower half of a combined median split. -/ def leftSize (nums1 nums2 : List Int) : Nat := (nums1.length + nums2.length + 1) / 2 /-- The lower part obtained by taking `i` elements from `nums1` and the rest from `nums2`. -/ def lowerPart (nums1 nums2 : List Int) (i : Nat) : List Int := nums1.take i ++ nums2.take (leftSize nums1 nums2 - i) /-- The upper part left after taking `i` elements from `nums1` and the rest from `nums2`. -/ def upperPart (nums1 nums2 : List Int) (i : Nat) : List Int := nums1.drop i ++ nums2.drop (leftSize nums1 nums2 - i) /-- `i` is a valid lower-half split when its parts have the right sizes and separate in order. -/ def IsMedianPartition (nums1 nums2 : List Int) (i : Nat) : Prop := i ≤ nums1.length ∧ i ≤ leftSize nums1 nums2 ∧ leftSize nums1 nums2 - i ≤ nums2.length ∧ ∀ x ∈ lowerPart nums1 nums2 i, ∀ y ∈ upperPart nums1 nums2 i, x ≤ y /-- The lower and upper parts of split `i` lie below and above `result` respectively. -/ def boundsMedian (nums1 nums2 : List Int) (i : Nat) (result : Rat) : Prop := (∀ x ∈ lowerPart nums1 nums2 i, (x : Rat) ≤ result) ∧ ∀ y ∈ upperPart nums1 nums2 i, result ≤ (y : Rat) /-- `result` is the boundary median determined by split `i` for the parity of the total length. -/ def isBoundaryMedian (nums1 nums2 : List Int) (i : Nat) (result : Rat) : Prop := ((nums1.length + nums2.length) % 2 = 1 → ∀ lo : Int, IsGreatest {x | x ∈ lowerPart nums1 nums2 i} lo → result = (lo : Rat)) ∧ ((nums1.length + nums2.length) % 2 = 0 → ∀ lo hi : Int, IsGreatest {x | x ∈ lowerPart nums1 nums2 i} lo → IsLeast {x | x ∈ upperPart nums1 nums2 i} hi → result = ((lo : Rat) + (hi : Rat)) / 2) /-- Computable sortedness decision for integer lists, obtained from core's finite-index decision procedure together with the decidable order comparison on `Int`. -/ instance instDecidableSortedLEInt (l : List Int) : Decidable (List.SortedLE l) := inferInstanceAs (Decidable (∀ a b : Fin l.length, a ≤ b → l.get a ≤ l.get b)) /-! ### Validity predicate (V) -/ /-- Valid input: both arrays sorted, within the length bounds, and with every entry in range. -/ def isValidInput (input : Input) : Bool := decide (List.SortedLE input.1) && decide (List.SortedLE input.2) && input.1.length ≤ 1000 && input.2.length ≤ 1000 && 1 ≤ input.1.length + input.2.length && input.1.length + input.2.length ≤ 2000 && input.1.all (fun x => -1000000 ≤ x && x ≤ 1000000) && input.2.all (fun x => -1000000 ≤ x && x ≤ 1000000) /-! ### Ideal specification (P_spec) -/ /-- `result` is bounded by some median split and is the boundary median of every such split. -/ def medianOfTwoSortedArrays_spec (input : Input) (result : Output) : Prop := (∃ i : Nat, IsMedianPartition input.1 input.2 i ∧ boundsMedian input.1 input.2 i result) ∧ ∀ i : Nat, IsMedianPartition input.1 input.2 i → boundsMedian input.1 input.2 i result → isBoundaryMedian input.1 input.2 i result /-! ### Decidable specification (P_check) -/ /-- The largest element of an integer list, if any. -/ def listMaxInt? (xs : List Int) : Option Int := xs.foldl (fun acc x => match acc with | none => some x | some m => some (max m x)) none /-- The smallest element of an integer list, if any. -/ def listMinInt? (xs : List Int) : Option Int := xs.foldl (fun acc x => match acc with | none => some x | some m => some (min m x)) none /-- Boolean form of `IsMedianPartition` for the executable checker. -/ def isMedianPartitionBool (nums1 nums2 : List Int) (i : Nat) : Bool := decide (i ≤ nums1.length) && decide (i ≤ leftSize nums1 nums2) && decide (leftSize nums1 nums2 - i ≤ nums2.length) && (lowerPart nums1 nums2 i).all fun x => (upperPart nums1 nums2 i).all fun y => decide (x ≤ y) /-- Boolean form of `boundsMedian` for the executable checker. -/ def boundsMedianBool (nums1 nums2 : List Int) (i : Nat) (result : Rat) : Bool := (lowerPart nums1 nums2 i).all (fun x => decide ((x : Rat) ≤ result)) && (upperPart nums1 nums2 i).all (fun y => decide (result ≤ (y : Rat))) /-- The boundary-median condition of split `i` realized through the maximum of the lower part and the minimum of the upper part, vacuously true when the relevant part is empty. -/ def matchesBoundaryMedian (nums1 nums2 : List Int) (i : Nat) (result : Rat) : Bool := if (nums1.length + nums2.length) % 2 = 1 then match listMaxInt? (lowerPart nums1 nums2 i) with | some lo => decide (result = (lo : Rat)) | none => true else match listMaxInt? (lowerPart nums1 nums2 i), listMinInt? (upperPart nums1 nums2 i) with | some lo, some hi => decide (result = ((lo : Rat) + (hi : Rat)) / 2) | _, _ => true /-- Executable checker for `medianOfTwoSortedArrays_spec`, with the split index truncated to the range forced by `IsMedianPartition`. -/ def medianOfTwoSortedArrays_check (input : Input) (result : Output) : Bool := (List.range (input.1.length + 1)).any (fun i => isMedianPartitionBool input.1 input.2 i && boundsMedianBool input.1 input.2 i result) && (List.range (input.1.length + 1)).all fun i => if isMedianPartitionBool input.1 input.2 i && boundsMedianBool input.1 input.2 i result then matchesBoundaryMedian input.1 input.2 i result else true theorem listMaxInt_eq_max? (xs : List Int) : listMaxInt? xs = xs.max? := by cases xs with | nil => rfl | cons a as => simp only [listMaxInt?, List.foldl_cons, List.max?] induction as generalizing a with | nil => rfl | cons b bs ih => simp only [List.foldl_cons] exact ih (max a b) theorem listMinInt_eq_min? (xs : List Int) : listMinInt? xs = xs.min? := by cases xs with | nil => rfl | cons a as => simp only [listMinInt?, List.foldl_cons, List.min?] induction as generalizing a with | nil => rfl | cons b bs ih => simp only [List.foldl_cons] exact ih (min a b) theorem max_some_iff (xs : List Int) (m : Int) : listMaxInt? xs = some m ↔ IsGreatest {x | x ∈ xs} m := by rw [listMaxInt_eq_max?] simpa only [IsGreatest, mem_upperBounds, Set.mem_setOf_eq] using (List.max?_eq_some_iff (xs := xs) (a := m)) theorem min_some_iff (xs : List Int) (m : Int) : listMinInt? xs = some m ↔ IsLeast {x | x ∈ xs} m := by rw [listMinInt_eq_min?] simpa only [IsLeast, mem_lowerBounds, Set.mem_setOf_eq] using (List.min?_eq_some_iff (xs := xs) (a := m)) theorem boundary_reflect (xs ys : List Int) (i : Nat) (r : Rat) : matchesBoundaryMedian xs ys i r = true ↔ isBoundaryMedian xs ys i r := by unfold matchesBoundaryMedian isBoundaryMedian rcases Nat.mod_two_eq_zero_or_one (xs.length + ys.length) with hp | hp · cases hx : listMaxInt? (lowerPart xs ys i) with | none => simp [hp, hx, ← max_some_iff, ← min_some_iff] | some lo => cases hy : listMinInt? (upperPart xs ys i) with | none => simp [hp, hx, hy, ← max_some_iff, ← min_some_iff] | some hi => simp [hp, hx, hy, ← max_some_iff, ← min_some_iff] · cases hx : listMaxInt? (lowerPart xs ys i) with | none => simp [hp, hx, ← max_some_iff, ← min_some_iff] | some lo => simp [hp, hx, ← max_some_iff, ← min_some_iff] theorem partition_reflect (xs ys : List Int) (i : Nat) : isMedianPartitionBool xs ys i = true ↔ IsMedianPartition xs ys i := by simp [isMedianPartitionBool, IsMedianPartition, and_assoc] theorem bounds_reflect (xs ys : List Int) (i : Nat) (r : Rat) : boundsMedianBool xs ys i r = true ↔ boundsMedian xs ys i r := by simp [boundsMedianBool, boundsMedian] theorem median_root (hb : ∀ (xs ys : List Int) (i : Nat) (r : Rat), matchesBoundaryMedian xs ys i r = true ↔ isBoundaryMedian xs ys i r) (input : Input) (result : Output) : medianOfTwoSortedArrays_check input result ↔ medianOfTwoSortedArrays_spec input result := by simp only [medianOfTwoSortedArrays_check, medianOfTwoSortedArrays_spec, Bool.and_eq_true, List.any_eq_true, List.all_eq_true, List.mem_range, Bool.ite_eq_true_distrib, Bool.and_eq_true, partition_reflect, bounds_reflect, hb, if_true_right, Nat.lt_succ_iff] have bound : ∀ i, IsMedianPartition input.1 input.2 i → i ≤ input.1.length := fun i hi => hi.1 grind only [] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem medianOfTwoSortedArrays_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : medianOfTwoSortedArrays_check input result ↔ medianOfTwoSortedArrays_spec input result := by exact median_root boundary_reflect input result /-! ### Implementation helpers -/ /-- The element of `xs` at index `k`, or `sentinel` when `k` is out of range. -/ def boundaryElement (xs : List Int) (k : Nat) (sentinel : Int) : Int := match xs[k]? with | some x => x | none => sentinel /-- The boundary data of split `i`: whether it is a median partition, whether the search must move to smaller indices, and the median the split yields. -/ def splitResult (xs ys : List Int) (i : Nat) : Bool × Bool × Rat := let j := leftSize xs ys - i let maxLeft1 := if i = 0 then -1000001 else boundaryElement xs (i - 1) (-1000001) let maxLeft2 := if j = 0 then -1000001 else boundaryElement ys (j - 1) (-1000001) let minRight1 := boundaryElement xs i 1000001 let minRight2 := boundaryElement ys j 1000001 if maxLeft1 ≤ minRight2 && maxLeft2 ≤ minRight1 then (true, false, if (xs.length + ys.length) % 2 = 1 then (max maxLeft1 maxLeft2 : Rat) else ((max maxLeft1 maxLeft2 : Rat) + (min minRight1 minRight2 : Rat)) / 2) else (false, maxLeft1 > minRight2, 0) /-- Binary search for the median partition over split indices `i ∈ [lo, lo + len]`. -/ def medianBinarySearch (xs ys : List Int) (lo len : Nat) : Rat := if h : len = 0 then (splitResult xs ys lo).2.2 else let i := lo + len / 2 let r := splitResult xs ys i if r.1 then r.2.2 else if r.2.1 then medianBinarySearch xs ys lo (len / 2 - 1) else medianBinarySearch xs ys (i + 1) (len - len / 2 - 1) termination_by len decreasing_by · simp_wf; omega · simp_wf; omega /-! ### Main algorithm (impl) -/ /-- Median of two sorted integer lists by binary search on the split index of the shorter list. -/ def findMedianSortedArrays (input : Input) : Output := if input.1.length ≤ input.2.length then medianBinarySearch input.1 input.2 0 input.1.length else medianBinarySearch input.2 input.1 0 input.2.length /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findMedianSortedArrays_correct (input : Input) (h : isValidInput input) : medianOfTwoSortedArrays_spec input (findMedianSortedArrays input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 3], [2]) #guard isValidInput ([1, 2], [3, 4]) #guard isValidInput ([2], []) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], [])) #guard !(isValidInput ([0, 1000001], [0])) #guard !(isValidInput ([(-1000001), 0], [0])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard medianOfTwoSortedArrays_check ([1, 3], [2]) 2.0 #guard medianOfTwoSortedArrays_check ([1, 2], [3, 4]) 2.5 #guard medianOfTwoSortedArrays_check ([2], []) 2.0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(medianOfTwoSortedArrays_check ([1, 3], [2]) 2.5) #guard !(medianOfTwoSortedArrays_check ([1, 2], [3, 4]) 2.0) #guard !(medianOfTwoSortedArrays_check ([2], []) 1.0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findMedianSortedArrays ([1, 3], [2]) == 2.0 #guard findMedianSortedArrays ([1, 2], [3, 4]) == 2.5 #guard findMedianSortedArrays ([2], []) == 2.0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard medianOfTwoSortedArrays_check ([1, 3], [2]) (findMedianSortedArrays ([1, 3], [2])) #guard medianOfTwoSortedArrays_check ([1, 2], [3, 4]) (findMedianSortedArrays ([1, 2], [3, 4])) #guard medianOfTwoSortedArrays_check ([2], []) (findMedianSortedArrays ([2], [])) end PMedianOfTwoSortedArrays