import Mathlib /-! # Search Insert Position Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. ## Constraints - 1 <= nums.length <= 10^4 - -10^4 <= nums[i] <= 10^4 - nums contains distinct values sorted in ascending order. - -10^4 <= target <= 10^4 ## Provided examples - `nums = [1, 3, 5, 6], target = 5` → `2` - `nums = [1, 3, 5, 6], target = 2` → `1` - `nums = [1, 3, 5, 6], target = 7` → `4` ## Synthesized negative examples - invalid input: `nums = [], target = 0` ([structural] a predicate that admits 1 <= nums.length <= 10^4. empty list; forgot the minimum length) - invalid input: `nums = [-10001], target = 0` ([structural] a predicate that admits -10^4 <= nums[i] <= 10^4. element one below the lower bound) - invalid input: `nums = [2, 1], target = 0` ([structural] a predicate that admits nums contains distinct values sorted in ascending order.. not sorted; checks distinctness alone accepts it) - `nums = [1, 3, 5, 6], target = 5` → `3` is wrong ([structural] The answer is not required to be the minimal index with nums[i] >= target; a larger feasible index is accepted.. 3 is the upper_bound, valid but not least.) - `nums = [1, 3, 5, 6], target = 2` → `2` is wrong ([structural] indices are not required to be zero-based. 1-based insertion position is 2.) - `nums = [1, 3, 5, 6], target = 7` → `0` is wrong ([structural] nothing requires answer to depend on target or array. always 0 satisfies a no-search specification) -/ namespace PSearchInsertPosition abbrev Input := (List Int) × (Int) abbrev Output := Nat /-! ### Specification helpers -/ /-- `i` is an insertion bound for `target` in `nums`: either `i = nums.length`, or `i < nums.length` and `target ≤ nums[i]!`. -/ def IsUpperBound (nums : List Int) (target : Int) (i : Nat) : Prop := i = nums.length ∨ i < nums.length ∧ target ≤ nums[i]! /-! ### Validity predicate (V) -/ /-- Valid input: 1 ≤ nums.length ≤ 10^4, elements in [-10^4, 10^4], pairwise distinct, sorted ascending, target in [-10^4, 10^4]. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.1.length ∧ input.1.length ≤ 10000) && input.1.all (fun x => decide (-10000 ≤ x ∧ x ≤ 10000)) && decide input.1.Nodup && decide (input.1.Pairwise fun a b => a ≤ b) && decide (-10000 ≤ input.2 ∧ input.2 ≤ 10000) /-! ### Ideal specification (P_spec) -/ /-- `result` is the least insertion bound: it is an upper bound for `target` in `nums`, and no smaller index is. -/ def searchInsert_spec (input : Input) (result : Output) : Prop := IsLeast {i | IsUpperBound input.1 input.2 i} result /-! ### Decidable specification (P_check) -/ /-- Decides `IsUpperBound nums target i` by unfolding it to a disjunction of a `Nat` equality and a bounded `Nat`/`Int` comparison, both of which Lean already decides. -/ instance (nums : List Int) (target : Int) (i : Nat) : Decidable (IsUpperBound nums target i) := inferInstanceAs (Decidable (i = nums.length ∨ i < nums.length ∧ target ≤ nums[i]!)) /-- Decides the least-insertion-bound property: `result` is an upper bound, and the unbounded "no smaller index is" (the `lowerBounds` half of `IsLeast`) is restated as the bounded, decidable `∀ i < result, ¬ IsUpperBound nums target i`, which `Nat.decidableBallLT` handles given the instance above. -/ instance (nums : List Int) (target : Int) (result : Nat) : Decidable (IsLeast {i | IsUpperBound nums target i} result) := decidable_of_iff (IsUpperBound nums target result ∧ ∀ i < result, ¬IsUpperBound nums target i) (by constructor · -- From the decidable form to `IsLeast`: any upper bound `b` satisfies -- `result ≤ b`, since `b < result` would contradict the bounded hypothesis. rintro ⟨hmem, hlt⟩ refine ⟨hmem, fun b hb => ?_⟩ rcases Nat.lt_or_ge b result with h | h · exact absurd hb (hlt b h) · exact h · -- From `IsLeast` to the decidable form: any `i < result` that is itself -- an upper bound contradicts `result ∈ lowerBounds`. rintro ⟨hmem, hlb⟩ refine ⟨hmem, fun i hi hub => ?_⟩ have hle : result ≤ i := hlb (show i ∈ {i | IsUpperBound nums target i} from hub) omega) /-- Executable checker obtained mechanically from the specification. -/ def searchInsert_check (input : Input) (result : Output) : Bool := @decide (searchInsert_spec input result) (by unfold searchInsert_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem searchInsert_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : searchInsert_check input result ↔ searchInsert_spec input result := by simp [searchInsert_check] /-! ### Implementation helpers -/ /-- Boolean decision of `IsUpperBound`: `i = nums.length`, or `i < nums.length` with `target ≤ nums[i]!`. -/ def upperBoundB (nums : List Int) (target : Int) (i : Nat) : Bool := i == nums.length || (decide (i < nums.length) && decide (target ≤ nums[i]!)) /-- Binary-search loop for the least upper-bound index in `[lo, hi]`, assuming `hi` is an upper bound and none is below `lo`. -/ def searchInsertAux (nums : List Int) (target : Int) (lo hi : Nat) : Nat := if h : lo < hi then if upperBoundB nums target (lo + (hi - lo) / 2) then searchInsertAux nums target lo (lo + (hi - lo) / 2) else searchInsertAux nums target (lo + (hi - lo) / 2 + 1) hi else lo termination_by hi - lo decreasing_by · simp_wf omega · simp_wf omega /-! ### Main algorithm (impl) -/ /-- Binary search for the least insertion bound of `target` in `nums`. -/ def searchInsertPosition (input : Input) : Output := searchInsertAux input.1 input.2 0 input.1.length /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem searchInsertPosition_correct (input : Input) (h : isValidInput input) : searchInsert_spec input (searchInsertPosition input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 3, 5, 6], 5) #guard isValidInput ([1, 3, 5, 6], 2) #guard isValidInput ([1, 3, 5, 6], 7) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 0)) #guard !(isValidInput ([(-10001)], 0)) #guard !(isValidInput ([2, 1], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard searchInsert_check ([1, 3, 5, 6], 5) 2 #guard searchInsert_check ([1, 3, 5, 6], 2) 1 #guard searchInsert_check ([1, 3, 5, 6], 7) 4 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(searchInsert_check ([1, 3, 5, 6], 5) 3) #guard !(searchInsert_check ([1, 3, 5, 6], 2) 2) #guard !(searchInsert_check ([1, 3, 5, 6], 7) 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard searchInsertPosition ([1, 3, 5, 6], 5) == 2 #guard searchInsertPosition ([1, 3, 5, 6], 2) == 1 #guard searchInsertPosition ([1, 3, 5, 6], 7) == 4 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard searchInsert_check ([1, 3, 5, 6], 5) (searchInsertPosition ([1, 3, 5, 6], 5)) #guard searchInsert_check ([1, 3, 5, 6], 2) (searchInsertPosition ([1, 3, 5, 6], 2)) #guard searchInsert_check ([1, 3, 5, 6], 7) (searchInsertPosition ([1, 3, 5, 6], 7)) end PSearchInsertPosition