"""
p34 — Find Minimum in Rotated Sorted Array (LeetCode 153).

Two implementations:
    find_min        — convergent-bounds binary search. O(log N).
    find_min_brute  — min(nums). ORACLE.

Run: python3 solution.py
"""
from __future__ import annotations
import random
from typing import List


# --------------------------------------------------------------------------------------
# Canonical: convergent-bounds binary search. O(log N).
# --------------------------------------------------------------------------------------
def find_min(nums: List[int]) -> int:
    lo, hi = 0, len(nums) - 1
    # INVARIANT: the minimum lies in nums[lo..hi] (inclusive).
    # We compare nums[mid] to nums[hi] (right anchor — handles unrotated cleanly):
    #   nums[mid] >  nums[hi]  → pivot is STRICTLY right of mid  → lo = mid + 1
    #   nums[mid] <= nums[hi]  → pivot is at mid or LEFT of mid → hi = mid
    # Loop condition is `lo < hi` (convergent), terminating with lo == hi == pivot idx.
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]


# --------------------------------------------------------------------------------------
# Brute oracle.
# --------------------------------------------------------------------------------------
def find_min_brute(nums: List[int]) -> int:
    return min(nums)


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    # Single element
    assert find_min([1]) == 1
    assert find_min([-5]) == -5

    # Unrotated
    assert find_min([1, 2, 3, 4, 5]) == 1
    assert find_min([11, 13, 15, 17]) == 11

    # LC canonical
    assert find_min([3, 4, 5, 1, 2]) == 1
    assert find_min([4, 5, 6, 7, 0, 1, 2]) == 0

    # Two-element
    assert find_min([2, 1]) == 1
    assert find_min([1, 2]) == 1

    # Rotated by 1
    assert find_min([5, 1, 2, 3, 4]) == 1

    # Rotated by N-1
    assert find_min([2, 3, 4, 5, 1]) == 1

    # Negatives
    assert find_min([3, 4, -2, -1, 0, 1, 2]) == -2
    assert find_min([-3, -2, -1, -5, -4]) == -5

    # Large rotation
    arr = list(range(1, 21))  # [1..20]
    for k in range(len(arr)):
        rotated = arr[k:] + arr[:k]
        assert find_min(rotated) == 1, f"failed at k={k}: {rotated}"

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(300):
        n = rng.randint(1, 20)
        pool = rng.sample(range(-50, 50), n)
        pool.sort()
        k = rng.randint(0, n - 1)
        nums = pool[k:] + pool[:k]
        a = find_min(nums)
        b = find_min_brute(nums)
        assert a == b, f"DISAGREE nums={nums}: find_min={a} min={b}"
    print("stress_test: 300 random rotated arrays — find_min and min agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")