Python Playground Code

readme.md

Interview Question: Finding an Element in a Rotated Sorted Array

Question:

You are given a rotated sorted array of unique integers, meaning the array was originally sorted in ascending order, but then some unknown number of elements were moved from the front to the back. Given this array, write a function search_rotated_array(nums: List[int], target: int) -> int that returns the index of the target in the array. If the target is not present, return -1.

You must write an efficient solution with a time complexity of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

---

file1.py

# This is an empty file

requirements.txt

pytest

search_rotated_array.py

from typing import List

def search_rotated_array(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Determine which side is sorted
        if nums[left] <= nums[mid]:  # Left side is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right side is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

test_search_rotated_array.py

import pytest
from search_rotated_array import search_rotated_array

@pytest.mark.parametrize("nums, target, expected", [
    # General cases
    ([4,5,6,7,0,1,2], 0, 4),
    ([4,5,6,7,0,1,2], 3, -1),
    ([1], 0, -1),
    
    # Edge cases
    ([1, 3, 5], 3, 1),
    ([2, 3, 4, 5, 6, 7, 8, 1], 8, 6),
    ([2, 3, 4, 5, 6, 7, 8, 1], 2, 0),
    ([7, 8, 1, 2, 3, 4, 5, 6], 3, 4),
    
    # Single element arrays
    ([1], 1, 0),
    ([1], 2, -1),
    
    # Two element arrays
    ([2, 1], 1, 1),
    ([2, 1], 2, 0),
    
    # Rotated arrays with large gaps
    ([30, 40, 50, 10, 20], 10, 3),
    ([30, 40, 50, 10, 20], 50, 2),
    
    # Searching for elements not in the array
    ([4,5,6,7,0,1,2], 8, -1),
    ([4,5,6,7,0,1,2], -1, -1),
    
    # Repeated element test for uniqueness check
    ([10, 20, 30, 40, 50, 60, 5], 60, 5),
    
    # Longer array
    ([15, 18, 2, 3, 6, 12], 15, 0),
    ([15, 18, 2, 3, 6, 12], 6, 4),
    
    # More complex rotations
    ([9,12,15,18,21,3,6], 21, 4),
    ([9,12,15,18,21,3,6], 6, 6),
])
def test_search_rotated_array(nums, target, expected):
    assert search_rotated_array(nums, target) == expected