Search Rotated Array¶
Problem¶
An array sorted in ascending order was rotated at some pivot. Given a target value, return its index or -1. All values are distinct.
Approach¶
Modified binary search. At each step, determine which half is sorted (compare nums[lo] to nums[mid]). Then check whether the target lies within the sorted half to decide which side to search.
When to Use¶
Invariant-based binary search — array is sorted but shifted/rotated. Identify which half is sorted, then decide which side to search. Keywords: "rotated sorted array", "shifted sequence", "cyclic order".
Complexity¶
| Time | O(log n) |
| Space | O(1) |
Implementation¶
search_rotated_array ¶
Search in rotated sorted array.
Problem
An array sorted in ascending order was rotated at some pivot. Given a target value, return its index or -1. All values are distinct.
Approach
Modified binary search. At each step, determine which half is sorted (compare nums[lo] to nums[mid]). Then check whether the target lies within the sorted half to decide which side to search.
When to use
Invariant-based binary search — array is sorted but shifted/rotated. Identify which half is sorted, then decide which side to search. Keywords: "rotated sorted array", "shifted sequence", "cyclic order".
Complexity
Time: O(log n) Space: O(1)
search_rotated ¶
Return the index of target in a rotated sorted array, or -1.
search_rotated([4, 5, 6, 7, 0, 1, 2], 0) 4 search_rotated([4, 5, 6, 7, 0, 1, 2], 3) -1 search_rotated([1], 1) 0
Source code in src/algo/searching/search_rotated_array.py
"""Tests for search in rotated sorted array."""
from hypothesis import given
from hypothesis import strategies as st
from algo.searching.search_rotated_array import search_rotated
class TestSearchRotated:
def test_found_in_right_half(self) -> None:
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 0) == 4
def test_found_in_left_half(self) -> None:
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 5) == 1
def test_not_found(self) -> None:
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 3) == -1
def test_single_element_found(self) -> None:
assert search_rotated([1], 1) == 0
def test_single_element_not_found(self) -> None:
assert search_rotated([1], 0) == -1
def test_not_rotated(self) -> None:
assert search_rotated([1, 2, 3, 4, 5], 3) == 2
def test_rotated_by_one(self) -> None:
assert search_rotated([5, 1, 2, 3, 4], 5) == 0
@given(
data=st.lists(
st.integers(min_value=-500, max_value=500),
min_size=1,
max_size=50,
unique=True,
),
pivot=st.integers(min_value=0, max_value=1000),
)
def test_finds_all_elements_in_rotated(self, data: list[int], pivot: int) -> None:
"""Every element should be found regardless of rotation amount."""
data.sort()
k = pivot % len(data)
rotated = data[k:] + data[:k]
for i, val in enumerate(rotated):
assert search_rotated(rotated, val) == i
Implement it yourself
Run: just challenge searching search_rotated_array
Then implement the functions to make all tests pass.
Use just study searching for watch mode.
Reveal Solution
search_rotated_array ¶
Search in rotated sorted array.
Problem
An array sorted in ascending order was rotated at some pivot. Given a target value, return its index or -1. All values are distinct.
Approach
Modified binary search. At each step, determine which half is sorted (compare nums[lo] to nums[mid]). Then check whether the target lies within the sorted half to decide which side to search.
When to use
Invariant-based binary search — array is sorted but shifted/rotated. Identify which half is sorted, then decide which side to search. Keywords: "rotated sorted array", "shifted sequence", "cyclic order".
Complexity
Time: O(log n) Space: O(1)
search_rotated ¶
Return the index of target in a rotated sorted array, or -1.
search_rotated([4, 5, 6, 7, 0, 1, 2], 0) 4 search_rotated([4, 5, 6, 7, 0, 1, 2], 3) -1 search_rotated([1], 1) 0