import Mathlib /-! # Search In Rotated Sorted Array Ii There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= 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,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4]. Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums. You must decrease the overall operation steps as much as possible. ## Constraints - 1 <= nums.length <= 5000 - -10^4 <= nums[i] <= 10^4 - nums is guaranteed to be rotated at some pivot. - -10^4 <= target <= 10^4 ## Provided examples - `nums = [2, 5, 6, 0, 0, 1, 2], target = 0` → `true` - `nums = [2, 5, 6, 0, 0, 1, 2], target = 3` → `false` - `nums = [1], target = 1` → `true` ## Synthesized negative examples - invalid input: `nums = [], target = 0` ([structural] a predicate that admits 1 <= nums.length <= 5000. empty array below minimum length) - invalid input: `nums = [10001], target = 0` ([structural] a predicate that admits -10^4 <= nums[i] <= 10^4. one past maximum element value) - invalid input: `nums = [3, 2, 1], target = 0` ([structural] a predicate that admits nums is guaranteed to be rotated at some pivot.. two descents; no rotation of a non-decreasing array) - `nums = [2, 5, 6, 0, 0, 1, 2], target = 0` → `false` is wrong ([structural] only requires false when target is absent, not true when present. false is accepted if only negative membership is required) - `nums = [2, 5, 6, 0, 0, 1, 2], target = 3` → `true` is wrong ([structural] specification omits the requirement to return false when target absent. true passes if only the positive direction is stated) - `nums = [1], target = 1` → `false` is wrong ([structural] a present target is never required to be reported; always-false satisfies a soundness-only reading. false is the degenerate no-search answer) -/ namespace PSearchInRotatedSortedArrayIi abbrev Input := (List Int) × (Int) abbrev Output := Bool /-! ### Specification helpers -/ /-- Number of strict descents between cyclically adjacent elements of `l`, counting the wrap from the last element to the first. -/ def countCyclicDescents (l : List Int) : Nat := (l.zip (l.rotate 1)).countP fun p => decide (p.2 < p.1) /-! ### Validity predicate (V) -/ /-- Valid input: `nums` has length in [1, 5000], entries and `target` lie in [-10^4, 10^4], and `nums` is a rotation of a non-decreasing sorted list. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 5000 && input.1.all (fun x => -10000 ≤ x && x ≤ 10000) && countCyclicDescents input.1 ≤ 1 && -10000 ≤ input.2 && input.2 ≤ 10000 /-! ### Ideal specification (P_spec) -/ /-- `result` holds exactly when `target` is an element of `nums`, in both directions. -/ def searchRotatedSortedArray_spec (input : Input) (result : Output) : Prop := result ↔ input.2 ∈ input.1 /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def searchRotatedSortedArray_check (input : Input) (result : Output) : Bool := @decide (searchRotatedSortedArray_spec input result) (by unfold searchRotatedSortedArray_spec; infer_instance) /-- 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] /-! ### Implementation helpers -/ /-- Recursive binary search of `a` over the inclusive index interval `[lo, hi]`. -/ def binarySearchRotated (a : Array Int) (target : Int) (lo hi : Nat) : Bool := if hle : lo ≤ hi then let mid := lo + (hi - lo) / 2 have hmid_lower : lo ≤ mid := by change lo ≤ lo + (hi - lo) / 2 omega have hmid_upper : mid ≤ hi := by change lo + (hi - lo) / 2 ≤ hi omega let first := a[lo]! let pivot := a[mid]! let last := a[hi]! if pivot = target then true else if hsingle : lo = hi then false else have hlohi : lo < hi := by omega if first = pivot ∧ pivot = last then binarySearchRotated a target (lo + 1) (hi - 1) else if first ≤ pivot then if first ≤ target ∧ target < pivot then if hleft : lo < mid then binarySearchRotated a target lo (mid - 1) else false else if hright : mid < hi then binarySearchRotated a target (mid + 1) hi else false else if pivot < target ∧ target ≤ last then if hright : mid < hi then binarySearchRotated a target (mid + 1) hi else false else if hleft : lo < mid then binarySearchRotated a target lo (mid - 1) else false else false termination_by hi - lo decreasing_by all_goals simp_wf omega /-! ### Main algorithm (impl) -/ /-- Binary search over the rotated array, shrinking around the known sorted half. -/ def searchInRotatedSortedArray (input : Input) : Output := let a := input.1.toArray if a.size = 0 then false else binarySearchRotated a input.2 0 (a.size - 1) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem searchInRotatedSortedArray_correct (input : Input) (h : isValidInput input) : searchRotatedSortedArray_spec input (searchInRotatedSortedArray input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([2, 5, 6, 0, 0, 1, 2], 0) #guard isValidInput ([2, 5, 6, 0, 0, 1, 2], 3) #guard isValidInput ([1], 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 0)) #guard !(isValidInput ([10001], 0)) #guard !(isValidInput ([3, 2, 1], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard searchRotatedSortedArray_check ([2, 5, 6, 0, 0, 1, 2], 0) true #guard searchRotatedSortedArray_check ([2, 5, 6, 0, 0, 1, 2], 3) false #guard searchRotatedSortedArray_check ([1], 1) true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(searchRotatedSortedArray_check ([2, 5, 6, 0, 0, 1, 2], 0) false) #guard !(searchRotatedSortedArray_check ([2, 5, 6, 0, 0, 1, 2], 3) true) #guard !(searchRotatedSortedArray_check ([1], 1) false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard searchInRotatedSortedArray ([2, 5, 6, 0, 0, 1, 2], 0) == true #guard searchInRotatedSortedArray ([2, 5, 6, 0, 0, 1, 2], 3) == false #guard searchInRotatedSortedArray ([1], 1) == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard searchRotatedSortedArray_check ([2, 5, 6, 0, 0, 1, 2], 0) (searchInRotatedSortedArray ([2, 5, 6, 0, 0, 1, 2], 0)) #guard searchRotatedSortedArray_check ([2, 5, 6, 0, 0, 1, 2], 3) (searchInRotatedSortedArray ([2, 5, 6, 0, 0, 1, 2], 3)) #guard searchRotatedSortedArray_check ([1], 1) (searchInRotatedSortedArray ([1], 1)) end PSearchInRotatedSortedArrayIi