Neural Mastery
← Practice
Search in Rotated Sorted Arrayeasy

Search in Rotated Sorted Array

easy Coding Interview Patterns 10–15 min

NumPy allowed · plain Python earns 10 bonus points

Interactive
Graph & Tree Traversal, Step by Step
Structure
Algorithm
ABCDE
visiting A -> visited order so far: [A]
queue now: [B, C]
Step 1 / 5
Both modes run the real algorithm from the linked practice problem, one step at a time -- edit the graph or pick different tree nodes and every step recomputes live.

Search for a target value in a sorted array that has been circularly rotated, maintaining O(log n) time complexity.

Related Skills

Task

Implement search_rotated_array(nums, target): determine which half of the array [lo..mid] or [mid..hi] is sorted, then check if target falls within that sorted segment to narrow down the search window.

Function Signature

search_rotated_array(nums: list[int], target: int) -> int

Examples

Example 1: Target Present in Rotated Array
Input: nums = [4, 5, 6, 7, 0, 1, 2] target = 0
Output: 4
Example 2: Target Not in Rotated Array
Input: nums = [4, 5, 6, 7, 0, 1, 2] target = 3
Output: -1

Constraints

  • 1 <= len(nums) <= 5000
  • -10^4 <= nums[i] <= 10^4
  • All values of nums are unique.
  • nums is guaranteed to be rotated at some pivot.
Python3Saved ✓
def search_rotated_array(nums: list[int], target: int) -> int:
"""nums: list of distinct integers sorted ascending, then rotated at an unknown pivot.
target: integer value to find.
Return index of target in nums, or -1 if not present. Must run in O(log n)."""
# Your implementation here
pass

Case 1: Target Present in Rotated Array
Input: nums = [4, 5, 6, 7, 0, 1, 2] target = 0
Expected: 4
Case 2: Target Not in Rotated Array
Input: nums = [4, 5, 6, 7, 0, 1, 2] target = 3
Expected: -1