Here’s a Python implementation of the search_rotated_array function:

from typing import List

def search_rotated_array(nums: List[int], target: int) -> int:
    if not nums:
        return -1

    low, high = 0, len(nums) - 1

    while low <= high:
        mid = (low + high) // 2

        if nums[mid] == target:
            return mid

        # Check which half is sorted
        if nums[low] <= nums[mid]:  # Left half is sorted
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:  # Right half is sorted
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1

    return -1

# Example usage:
nums = [4, 5, 6, 7, 0, 1, 2]
target1 = 0
target2 = 3

result1 = search_rotated_array(nums, target1)
print(result1)  # Output: 4

result2 = search_rotated_array(nums, target2)
print(result2)  # Output: -1

This solution performs a modified binary search to find the target in a rotated sorted array. The time complexity is O(log(n)), where n is the length of the array, and the space complexity is O(1).

Time Complexity:

Here’s a breakdown of the time complexity:

  1. Binary Search:
    • The main part of the algorithm is the binary search in a rotated sorted array.
    • In each iteration of the while loop, the search space is effectively halved.
    • This is a characteristic of binary search, leading to a logarithmic time complexity.
  2. Reducing Search Space:
    • In each iteration, the algorithm determines which half of the array is sorted by comparing the values at the extremes (low, mid, and high indices).
    • It then checks if the target is within the sorted half, effectively narrowing down the search space.
  3. Overall Time Complexity:
    • Since the search space is halved in each iteration, the time complexity of the binary search portion is O(log(n)).
    • Therefore, the overall time complexity of the search_rotated_array function is O(log(n)). This makes the algorithm efficient for searching in rotated sorted arrays, as it avoids checking every element individually.

In summary, the solution achieves an efficient O(log(n)) time complexity by employing a modified binary search.

Space complexity:

  • The algorithm uses a constant amount of extra space, regardless of the size of the input array.
  • The variables low, high, and mid are integers, and their memory consumption is constant.

The solution maintains a low O(1) space complexity by using a constant amount of additional memory.