jymchng · December 23, 2024 16:48 · Dec 23, 2024
diff --git a/readme.md b/readme.md
@@ -0,0 +1,26 @@
+### 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
+```
+---
diff --git a/requirements.txt b/requirements.txt
@@ -0,0 +1 @@
+pytest
diff --git a/search_rotated_array.py b/search_rotated_array.py
@@ -0,0 +1,24 @@
+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
diff --git a/test_search_rotated_array.py b/test_search_rotated_array.py
@@ -0,0 +1,44 @@
+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
No results found