60 lines
1.6 KiB
Python
60 lines
1.6 KiB
Python
"""Search in a rotated sorted array (possibly with duplicates).
|
|
|
|
Provides:
|
|
- find_pivot(nums): index of smallest element (rotation point), or -1 if not rotated
|
|
- search(nums, target): index of target or -1
|
|
- count_rotations(nums): number of rotations (== pivot index)
|
|
|
|
Handles empty, single element, duplicates, and arrays that are not rotated.
|
|
O(log n) typical; degrades to O(n) only when duplicates force linear scan
|
|
(standard limitation of rotated search with duplicates).
|
|
"""
|
|
from typing import List
|
|
|
|
|
|
def find_pivot(nums: List[int]) -> int:
|
|
"""Return index of the minimum element. -1 if nums is empty."""
|
|
if not nums:
|
|
return -1
|
|
lo, hi = 0, len(nums) - 1
|
|
# If already sorted (no rotation), pivot is 0.
|
|
if nums[lo] < nums[hi] or len(nums) == 1:
|
|
return 0
|
|
while lo < hi:
|
|
mid = (lo + hi) // 2
|
|
if nums[mid] > nums[hi]:
|
|
lo = mid + 1
|
|
elif nums[mid] < nums[hi]:
|
|
hi = mid
|
|
else:
|
|
# nums[mid] == nums[hi]: cannot decide; shrink hi
|
|
hi -= 1
|
|
return lo
|
|
|
|
|
|
def count_rotations(nums: List[int]) -> int:
|
|
p = find_pivot(nums)
|
|
return 0 if p < 0 else p
|
|
|
|
|
|
def search(nums: List[int], target: int) -> int:
|
|
if not nums:
|
|
return -1
|
|
pivot = find_pivot(nums)
|
|
n = len(nums)
|
|
# Map logical (sorted) index -> physical index.
|
|
def phys(i):
|
|
return (pivot + i) % n
|
|
|
|
lo, hi = 0, n - 1
|
|
while lo <= hi:
|
|
mid = (lo + hi) // 2
|
|
val = nums[phys(mid)]
|
|
if val == target:
|
|
return phys(mid)
|
|
if val < target:
|
|
lo = mid + 1
|
|
else:
|
|
hi = mid - 1
|
|
return -1
|