import Mathlib /-! # Search A 2D Matrix You are given an m x n integer matrix matrix with the following two properties: Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise. You must write a solution in O(log(m * n)) time complexity. ## Constraints - m == matrix.length - n == matrix[i].length - 1 <= m, n <= 100 - -10^4 <= matrix[i][j], target <= 10^4 ## Provided examples - `matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3` → `true` - `matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13` → `false` - `matrix = [[1]], target = 1` → `true` ## Synthesized negative examples - invalid input: `matrix = [[10001]], target = 0` ([structural] a predicate that admits -10^4 <= matrix[i][j], target <= 10^4. matrix entry one past the stated maximum) - invalid input: `matrix = [], target = 0` ([structural] a predicate that admits 1 <= m, n <= 100. empty matrix one row below the minimum m) - invalid input: `matrix = [[1, 2], [3]], target = 0` ([structural] a predicate that admits n == matrix[i].length. ragged rows; a predicate checking only row 0 accepts it) - `matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3` → `false` is wrong ([structural] membership is checked only against the first column. target 3 not in first column) - `matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13` → `true` is wrong ([structural] membership interpreted as lying between matrix min and max. 13 is in range but not in matrix) - `matrix = [[1]], target = 1` → `false` is wrong ([structural] Specification treats the single-element matrix as empty. A 1x1 matrix with matching target is rejected) -/ namespace PSearchA2dMatrix abbrev Input := (List (List Int)) × (Int) abbrev Output := Bool /-! ### Specification helpers -/ /-- A row is non-decreasing when each entry is at most the one after it. -/ def rowSorted : List Int → Bool | [] => true | a :: b :: rest => (a ≤ b) && rowSorted (b :: rest) | [_] => true /-- Each row's first entry is greater than the previous row's last entry. -/ def rowsJump : List (List Int) → Bool | [] => true | a :: b :: rest => (match a.getLast?, b.head? with | some x, some y => x < y | _, _ => false) && rowsJump (b :: rest) | [_] => true /-! ### Validity predicate (V) -/ /-- Valid input: a non-empty matrix of at most 100 equal-length non-empty sorted rows of at most 100 bounded entries each, each row starting strictly above the previous row's last entry, with a bounded target. -/ def isValidInput (input : Input) : Bool := let matrix := input.1 let target := input.2 match matrix with | [] => false | row0 :: _ => matrix.length ≤ 100 && matrix.all (fun row => 1 ≤ row.length && row.length ≤ 100 && row.length == row0.length && rowSorted row && row.all (fun x => -10000 ≤ x && x ≤ 10000)) && rowsJump matrix && -10000 ≤ target && target ≤ 10000 /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when `target` is one of the entries of `matrix`. -/ def searchMatrix_spec (input : Input) (result : Output) : Prop := result ↔ input.2 ∈ input.1.flatten /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def searchMatrix_check (input : Input) (result : Output) : Bool := @decide (searchMatrix_spec input result) (by unfold searchMatrix_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem searchMatrix_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : searchMatrix_check input result ↔ searchMatrix_spec input result := by simp [searchMatrix_check] /-! ### Implementation helpers -/ /-- Entry at flat index `i`, with row `i / rowLength` and column `i % rowLength`. -/ def flatIndexElement (matrix : List (List Int)) (rowLength i : Nat) : Int := (matrix[i / rowLength]?.bind fun row => row[i % rowLength]?).getD 0 /-- Binary membership search over the half-open flat interval `[lo, hi)`. -/ def binarySearch (matrix : List (List Int)) (rowLength : Nat) (target : Int) (lo hi : Nat) : Bool := if h : hi ≤ lo then false else let mid := lo + (hi - lo) / 2 let x := flatIndexElement matrix rowLength mid if x = target then true else if target < x then binarySearch matrix rowLength target lo mid else binarySearch matrix rowLength target (mid + 1) hi termination_by hi - lo decreasing_by all_goals omega /-! ### Main algorithm (impl) -/ /-- Membership by binary search over the row-major flattened sorted matrix. -/ def searchMatrixContains (input : Input) : Output := let matrix := input.1 let target := input.2 match matrix with | [] => false | row0 :: _ => let rowLength := row0.length if rowLength = 0 then false else binarySearch matrix rowLength target 0 (matrix.length * rowLength) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem searchMatrixContains_correct (input : Input) (h : isValidInput input) : searchMatrix_spec input (searchMatrixContains input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3) #guard isValidInput ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13) #guard isValidInput ([[1]], 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([[10001]], 0)) #guard !(isValidInput ([], 0)) #guard !(isValidInput ([[1, 2], [3]], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard searchMatrix_check ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3) true #guard searchMatrix_check ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13) false #guard searchMatrix_check ([[1]], 1) true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(searchMatrix_check ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3) false) #guard !(searchMatrix_check ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13) true) #guard !(searchMatrix_check ([[1]], 1) false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard searchMatrixContains ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3) == true #guard searchMatrixContains ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13) == false #guard searchMatrixContains ([[1]], 1) == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard searchMatrix_check ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3) (searchMatrixContains ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3)) #guard searchMatrix_check ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13) (searchMatrixContains ([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13)) #guard searchMatrix_check ([[1]], 1) (searchMatrixContains ([[1]], 1)) end PSearchA2dMatrix