Skip to content
Hello Python

Search a Rotated Sorted Array

Interview ProblemIntermediateMediumArrayBinary Search

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.search(nums, target). nums contains distinct integers and was produced by rotating an ascending array zero or more positions. Return the target index or -1 in O(log n) time.

Starter code

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        pass
Test cases

rotated-found

{
  "args": [
    [
      4,
      5,
      6,
      7,
      0,
      1,
      2
    ],
    0
  ]
}

Expected: 4

Wizard outline
  1. Step 1: Initialize Solution.search

    Replace the empty starter with the first real state owned by Solution.search. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

  2. Step 2: Pass the Rotated Found case

    Complete the readable core algorithm for one representative Interview case. At every midpoint identify one sorted half and discard the half that cannot contain the target.

  3. Step 3: Harden the Two Elements boundary

    Repair the reviewed boundary and pass the complete submission contract. Distinct values guarantee at least one half is sorted. Endpoint comparisons determine whether the target can be in that half, so each update preserves the target if present while halving the search space.

Footguns and prerequisites
  • Use <= when detecting the sorted left half so a one-element left half is handled correctly.
  • arrays strings two pointers sliding window
Reviewed references
Practice prerequisites
  • Find the First True Boundary(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing search rotated array as a complete Interview Problem.

Recommended approach and implementation

Run binary search; at each midpoint identify the sorted half and keep it only when its endpoint range contains the target.

Why it works: Distinct values guarantee at least one half is sorted. Endpoint comparisons determine whether the target can be in that half, so each update preserves the target if present while halving the search space.

class Solution:
    def search(self, nums, target):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        left = 0
        right = len(nums) - 1
        while left <= right:
            middle = (left + right) // 2
            if nums[middle] == target:
                return middle
            if nums[left] <= nums[middle]:
                if nums[left] <= target < nums[middle]:
                    right = middle - 1
                else:
                    left = middle + 1
            else:
                if nums[middle] < target <= nums[right]:
                    left = middle + 1
                else:
                    right = middle - 1
        return -1