"""
p33 — Search in Rotated Sorted Array (LeetCode 33).

Two implementations:
    search        — one-pass rotated binary search. O(log N).
    search_brute  — linear scan. ORACLE.

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


# --------------------------------------------------------------------------------------
# Canonical: one-pass rotated binary search. O(log N).
# --------------------------------------------------------------------------------------
def search(nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    # INVARIANT: target, if present, lies in nums[lo..hi] (inclusive).
    # At each step exactly one of [lo..mid] or [mid+1..hi] is sorted (since
    # there is at most one drop in a rotated sorted array, and `mid` is in
    # exactly one of the two halves).
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        # Decide which half is sorted by comparing nums[mid] to nums[lo].
        if nums[lo] <= nums[mid]:
            # Left half [lo..mid] is sorted.
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # Right half [mid+1..hi] is sorted.
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


# --------------------------------------------------------------------------------------
# Brute oracle: linear scan.
# --------------------------------------------------------------------------------------
def search_brute(nums: List[int], target: int) -> int:
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    # Empty
    assert search([], 5) == -1

    # Single element
    assert search([1], 0) == -1
    assert search([1], 1) == 0

    # Unrotated
    assert search([1, 2, 3, 4, 5], 3) == 2
    assert search([1, 2, 3, 4, 5], 1) == 0
    assert search([1, 2, 3, 4, 5], 5) == 4
    assert search([1, 2, 3, 4, 5], 6) == -1

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

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

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

    # Two-element rotated
    assert search([3, 1], 1) == 1
    assert search([3, 1], 3) == 0
    assert search([1, 3], 3) == 1

    # Target absent in rotated
    assert search([6, 7, 0, 1, 2, 4, 5], 3) == -1

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(300):
        n = rng.randint(0, 20)
        # Build a sorted distinct array and rotate it by random k.
        if n == 0:
            nums: List[int] = []
        else:
            # Sample n distinct ints from a wider range.
            pool = rng.sample(range(-50, 50), n)
            pool.sort()
            k = rng.randint(0, n - 1)
            nums = pool[k:] + pool[:k]
        # Pick targets: half from inside, half outside.
        if nums and rng.random() < 0.6:
            target = rng.choice(nums)
        else:
            target = rng.randint(-100, 100)
        a = search(nums, target)
        b = search_brute(nums, target)
        # `search` may return any valid index; LC guarantees distinct so a unique index.
        # If target absent, both must be -1.
        assert (a == -1) == (b == -1), f"DISAGREE presence nums={nums} target={target} search={a} brute={b}"
        if a != -1:
            assert nums[a] == target, f"WRONG INDEX nums={nums} target={target} search={a}"
    print("stress_test: 300 random rotated arrays — search and brute agree on presence and value.")


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