import Mathlib /-! # Find First And Last Position Of Element In Sorted Array Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. ## Constraints - 0 <= nums.length <= 10^5 - -10^9 <= nums[i] <= 10^9 - nums is a non-decreasing array. - -10^9 <= target <= 10^9 ## Provided examples - `nums = [5, 7, 7, 8, 8, 10], target = 8` → `[3, 4]` - `nums = [5, 7, 7, 8, 8, 10], target = 6` → `[-1, -1]` - `nums = [], target = 0` → `[-1, -1]` ## Synthesized negative examples - invalid input: `nums = [1000000001], target = 0` ([structural] a predicate that admits -10^9 <= nums[i] <= 10^9. one past the stated maximum for nums[i]) - invalid input: `nums = [3, 2, 1], target = 2` ([structural] a predicate that admits nums is a non-decreasing array.. strictly descending, so not non-decreasing) - invalid input: `nums = [1], target = 1000000001` ([structural] a predicate that admits -10^9 <= target <= 10^9. target one past the stated maximum) - `nums = [5, 7, 7, 8, 8, 10], target = 8` → `[4, 5]` is wrong ([structural] indices are assumed 1-based rather than 0-based. one greater than true positions under 0-based indexing) - `nums = [5, 7, 7, 8, 8, 10], target = 6` → `[1, 1]` is wrong ([structural] if-target-not-found sentinel clause is dropped. target would be inserted at index 1) - `nums = [], target = 0` → `[0, -1]` is wrong ([structural] the not-found fallback is interpreted as an empty range at the insertion point (0-based). target absent, so an empty range is accepted instead of [-1,-1]) -/ namespace PFindFirstAndLastPositionOfElementInSortedArray abbrev Input := (List Int) × (Int) abbrev Output := List Int /-! ### Specification helpers -/ /-- The set of in-bounds 0-based indices of `nums` whose value equals `target`. -/ def TargetIndices (nums : List Int) (target : Int) : Set Nat := {i | ∃ h : i < nums.length, nums[i] = target} /-! ### Validity predicate (V) -/ /-- Valid input: at most `10^5` elements, each in `[-10^9, 10^9]`, sorted non-decreasing, with `target` in `[-10^9, 10^9]`. -/ def isValidInput (input : Input) : Bool := input.1.length ≤ 100000 && input.1.all (fun x => -1000000000 ≤ x && x ≤ 1000000000) && (input.1.zip input.1.tail).all (fun p => p.1 ≤ p.2) && -1000000000 ≤ input.2 && input.2 ≤ 1000000000 /-! ### Ideal specification (P_spec) -/ /-- `result` has length 2 and is either the sentinel `[-1, -1]` when `target` does not occur, or `[l, r]` where `l` and `r` are the least and greatest indices at which `target` occurs. -/ def searchRange_spec (input : Input) (result : Output) : Prop := result.length = 2 ∧ ((TargetIndices input.1 input.2 = ∅ ∧ result = [-1, -1]) ∨ ∃ l r : Nat, result = [(l : Int), (r : Int)] ∧ IsLeast (TargetIndices input.1 input.2) l ∧ IsGreatest (TargetIndices input.1 input.2) r) /-! ### Decidable specification (P_check) -/ /-- The list of in-bounds 0-based positions of `nums` holding `target`. -/ def targetPositions (nums : List Int) (target : Int) : List Nat := (List.range nums.length).filter fun i => nums[i]? = some target /-- Executable checker for `searchRange_spec` over the finite position list. -/ def searchRange_check (input : Input) (result : Output) : Bool := let S := targetPositions input.1 input.2 result.length == 2 && ((S.isEmpty && result == [-1, -1]) || S.any fun l => S.any fun r => result == [(l : Int), (r : Int)] && S.all (fun j => decide (l ≤ j)) && S.all (fun j => decide (j ≤ r))) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem searchRange_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : searchRange_check input result ↔ searchRange_spec input result := by simp [searchRange_check, searchRange_spec, targetPositions, TargetIndices, IsLeast, IsGreatest, lowerBounds, upperBounds, List.getElem?_eq_some_iff, Set.ext_iff] <;> grind only [] /-! ### Implementation helpers -/ /-- Leftmost index in `[lo, hi)` at which `nums` holds a value at least `target`, or `hi` when there is none; binary search. -/ def firstGE (nums : List Int) (target : Int) (lo hi : Nat) : Nat := if h : lo < hi then match nums[(lo + hi) / 2]? with | some v => if target ≤ v then firstGE nums target lo ((lo + hi) / 2) else firstGE nums target ((lo + hi) / 2 + 1) hi | none => firstGE nums target lo ((lo + hi) / 2) else lo termination_by hi - lo decreasing_by all_goals (simp_wf; omega) /-- Leftmost index in `[lo, hi)` at which `nums` holds a value greater than `target`, or `hi` when there is none; binary search. -/ def firstGT (nums : List Int) (target : Int) (lo hi : Nat) : Nat := if h : lo < hi then match nums[(lo + hi) / 2]? with | some v => if target < v then firstGT nums target lo ((lo + hi) / 2) else firstGT nums target ((lo + hi) / 2 + 1) hi | none => firstGT nums target lo ((lo + hi) / 2) else lo termination_by hi - lo decreasing_by all_goals (simp_wf; omega) /-! ### Main algorithm (impl) -/ /-- Two binary searches: the first index holding at least `target` and the first holding more than `target` delimit the answer. -/ def findFirstAndLastPosition (input : Input) : Output := let nums := input.1 let n := nums.length let i := firstGE nums input.2 0 n let j := firstGT nums input.2 0 n if i < n ∧ nums[i]? = some input.2 then [(i : Int), ((j - 1 : Nat) : Int)] else [-1, -1] /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findFirstAndLastPosition_correct (input : Input) (h : isValidInput input) : searchRange_spec input (findFirstAndLastPosition input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([5, 7, 7, 8, 8, 10], 8) #guard isValidInput ([5, 7, 7, 8, 8, 10], 6) #guard isValidInput ([], 0) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([1000000001], 0)) #guard !(isValidInput ([3, 2, 1], 2)) #guard !(isValidInput ([1], 1000000001)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard searchRange_check ([5, 7, 7, 8, 8, 10], 8) [3, 4] #guard searchRange_check ([5, 7, 7, 8, 8, 10], 6) [(-1), (-1)] #guard searchRange_check ([], 0) [(-1), (-1)] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(searchRange_check ([5, 7, 7, 8, 8, 10], 8) [4, 5]) #guard !(searchRange_check ([5, 7, 7, 8, 8, 10], 6) [1, 1]) #guard !(searchRange_check ([], 0) [0, (-1)]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findFirstAndLastPosition ([5, 7, 7, 8, 8, 10], 8) == [3, 4] #guard findFirstAndLastPosition ([5, 7, 7, 8, 8, 10], 6) == [-1, -1] #guard findFirstAndLastPosition ([], 0) == [-1, -1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard searchRange_check ([5, 7, 7, 8, 8, 10], 8) (findFirstAndLastPosition ([5, 7, 7, 8, 8, 10], 8)) #guard searchRange_check ([5, 7, 7, 8, 8, 10], 6) (findFirstAndLastPosition ([5, 7, 7, 8, 8, 10], 6)) #guard searchRange_check ([], 0) (findFirstAndLastPosition ([], 0)) end PFindFirstAndLastPositionOfElementInSortedArray