import Mathlib /-! # Search In Rotated Sorted Array There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity. ## Constraints - 1 <= nums.length <= 5000 - -10^4 <= nums[i] <= 10^4 - All values of nums are unique. - nums is an ascending array that is possibly rotated. - -10^4 <= target <= 10^4 ## Provided examples - `nums = [4, 5, 6, 7, 0, 1, 2], target = 0` → `4` - `nums = [4, 5, 6, 7, 0, 1, 2], target = 3` → `-1` - `nums = [1], target = 0` → `-1` ## Synthesized negative examples - invalid input: `nums = [], target = 0` ([structural] a predicate that admits 1 <= nums.length <= 5000. empty where at least one element is required) - invalid input: `nums = [10001], target = 0` ([structural] a predicate that admits -10^4 <= nums[i] <= 10^4. one past the stated maximum element) - invalid input: `nums = [1, 2, 1], target = 0` ([structural] a predicate that admits All values of nums are unique.. rotated duplicate; checks rotation but not uniqueness accepts it) - `nums = [4, 5, 6, 7, 0, 1, 2], target = 0` → `5` is wrong ([structural] omits the zero-based indexing requirement. zero-based index 4 is one-based index 5) - `nums = [4, 5, 6, 7, 0, 1, 2], target = 3` → `-2` is wrong ([structural] off-by-one in the not-found sentinel; returns -2 instead of -1. Target absent; sentinel one step below -1.) - `nums = [1], target = 0` → `0` is wrong ([structural] unattainable does not fit because this is not an optimization; the search loop returns the low index on failure instead of the -1 sentinel. target absent; returning 0 is one more than -1) -/ namespace PSearchInRotatedSortedArray abbrev Input := (List Int) × (Int) abbrev Output := Int /-! ### Specification helpers -/ /-- `idx` is a zero-based position in `nums` at which the value `target` stands. -/ def IsAtIndex (nums : List Int) (target : Int) (idx : Int) : Prop := 0 ≤ idx ∧ nums[idx.toNat]? = some target /-- The number of positions at which `l` drops below its cyclic successor. -/ def numDescents (l : List Int) : Nat := (l.zip (l.drop 1 ++ l.take 1)).countP fun p => decide (p.2 < p.1) /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 5000 distinct elements in [-10^4, 10^4] forming a rotated ascending array, with target in [-10^4, 10^4]. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.1.length) && decide (input.1.length ≤ 5000) && input.1.all (fun x => decide (-10000 ≤ x ∧ x ≤ 10000)) && (input.1.eraseDup.length == input.1.length) && decide (numDescents input.1 ≤ 1) && decide (-10000 ≤ input.2 ∧ input.2 ≤ 10000) /-! ### Ideal specification (P_spec) -/ /-- `result` is -1 or an index of `target` in `nums`; it is -1 exactly when `target` is absent, and every index at which `target` stands equals `result`. -/ def searchRotatedSortedArray_spec (input : Input) (result : Output) : Prop := (result = -1 ∨ IsAtIndex input.1 input.2 result) ∧ ((result = -1 ↔ input.2 ∉ input.1) ∧ ∀ i : Int, IsAtIndex input.1 input.2 i → i = result) /-! ### Decidable specification (P_check) -/ /-- Executable checker for `searchRotatedSortedArray_spec`, with the index quantifier truncated to the in-bounds positions `Fin input.1.length`. -/ def searchRotatedSortedArray_check (input : Input) (result : Output) : Bool := let nums := input.1 let target := input.2 (result == -1 || (decide (0 ≤ result) && nums[result.toNat]? == some target)) && ((result == -1) == !(nums.contains target)) && (List.range nums.length).all fun i => !(nums[i]? == some target) || (i : Int) == result /-- Interpret `f - n` for a partially applied checker as `f (-n)`, so the frozen specification guards that pass negative outputs elaborate as written. -/ instance hSubOutputBool : HSub (Output → Bool) Nat Bool where hSub f n := f (-(n : Int)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem searchRotatedSortedArray_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : searchRotatedSortedArray_check input result ↔ searchRotatedSortedArray_spec input result := by simp [searchRotatedSortedArray_check, searchRotatedSortedArray_spec, IsAtIndex, List.all_eq_true, List.mem_range] rw [Bool.eq_iff_iff] simp constructor · rintro ⟨⟨ha, hb⟩, hc⟩ refine ⟨ha, hb, ?_⟩ intro i hi he have hlt : i.toNat < input.1.length := (List.getElem?_eq_some_iff.mp he).1 have hx := hc i.toNat hlt simp only [he, beq_self_eq_true, Bool.not_true, Bool.false_eq_true, false_or, Int.toNat_of_nonneg hi] at hx simpa using hx · rintro ⟨ha, hb, hc⟩ refine ⟨⟨ha, hb⟩, ?_⟩ intro i hi by_cases he : input.1[i]? = some input.2 · right exact hc (i : Int) (by omega) (by simpa using he) · left simpa using he /-! ### Implementation helpers -/ /-- Recursive search for `target` in the half-open index interval `[lo, hi)`, narrowing into the sorted half. -/ def findInRotatedAux (nums : List Int) (target : Int) (lo hi : Nat) : Int := if h : lo < hi then let mid := lo + (hi - lo) / 2 have hlo : lo ≤ mid := Nat.le_add_right lo ((hi - lo) / 2) have hhi : mid < hi := by have hpos : 0 < hi - lo := Nat.sub_pos_of_lt h omega match nums[mid]? with | some mv => if mv = target then (mid : Int) else let lv := (nums[lo]?).getD mv let hv := (nums[hi - 1]?).getD mv if lv ≤ mv then if lv ≤ target ∧ target < mv then findInRotatedAux nums target lo mid else findInRotatedAux nums target (mid + 1) hi else if mv < target ∧ target ≤ hv then findInRotatedAux nums target (mid + 1) hi else findInRotatedAux nums target lo mid | none => -1 else -1 termination_by hi - lo decreasing_by all_goals omega /-! ### Main algorithm (impl) -/ /-- Binary search for `target` in the rotated ascending array, probing one midpoint per step and returning its index or -1. -/ def findInRotatedSortedArray (input : Input) : Output := findInRotatedAux input.1 input.2 0 input.1.length /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findInRotatedSortedArray_correct (input : Input) (h : isValidInput input) : searchRotatedSortedArray_spec input (findInRotatedSortedArray input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([4, 5, 6, 7, 0, 1, 2], 0) #guard isValidInput ([4, 5, 6, 7, 0, 1, 2], 3) #guard isValidInput ([1], 0) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 0)) #guard !(isValidInput ([10001], 0)) #guard !(isValidInput ([1, 2, 1], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard searchRotatedSortedArray_check ([4, 5, 6, 7, 0, 1, 2], 0) 4 #guard searchRotatedSortedArray_check ([4, 5, 6, 7, 0, 1, 2], 3) -1 #guard searchRotatedSortedArray_check ([1], 0) -1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(searchRotatedSortedArray_check ([4, 5, 6, 7, 0, 1, 2], 0) 5) #guard !(searchRotatedSortedArray_check ([4, 5, 6, 7, 0, 1, 2], 3) -2) #guard !(searchRotatedSortedArray_check ([1], 0) 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findInRotatedSortedArray ([4, 5, 6, 7, 0, 1, 2], 0) == 4 #guard findInRotatedSortedArray ([4, 5, 6, 7, 0, 1, 2], 3) == (-1) #guard findInRotatedSortedArray ([1], 0) == (-1) /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard searchRotatedSortedArray_check ([4, 5, 6, 7, 0, 1, 2], 0) (findInRotatedSortedArray ([4, 5, 6, 7, 0, 1, 2], 0)) #guard searchRotatedSortedArray_check ([4, 5, 6, 7, 0, 1, 2], 3) (findInRotatedSortedArray ([4, 5, 6, 7, 0, 1, 2], 3)) #guard searchRotatedSortedArray_check ([1], 0) (findInRotatedSortedArray ([1], 0)) end PSearchInRotatedSortedArray