Search in Rotated Sorted Array Using Binary Search

Problem Statement:
Given a sorted array that has been rotated at an unknown index, find the index of a target element. If the target is not present, return -1.

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

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

Approach:
We use a modified Binary Search. In a rotated sorted array, at least one half is always sorted. By checking which half is sorted, we can decide where the target might lie and reduce the search space.

Code:

def search(nums, target):
low = 0
high = len(nums) - 1

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

    if nums[mid] == target:
        return mid

    if nums[low] <= nums[mid]:
        if nums[low] <= target < nums[mid]:
            high = mid - 1
        else:
            low = mid + 1
    else:
        if nums[mid] < target <= nums[high]:
            low = mid + 1
        else:
            high = mid - 1

return -1

Explanation:
The algorithm first checks the middle element. Then it determines whether the left half or right half is sorted. Based on where the target lies, it continues the search in the correct half.

Time Complexity:
O(log n)

Space Complexity:
O(1)