Search in a Rotated Sorted Array

Problem

You are given a sorted array nums with distinct values, which might have been rotated at an unknown pivot.
Your task: find the index of a target number, or return -1 if it is not present.

The algorithm must run in O(log n) time.

Examples

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

Input
nums = [1], target = 0

Output
-1

Approach

Use modified binary search:

Initialize low = 0 and high = n-1.
While low <= high, find mid = (low + high) // 2.
If nums[mid] == target, return mid.
Determine which side is sorted:
If left side is sorted (nums[low] <= nums[mid]), check if target is in [low, mid].
Else, target must be in the right side.
Adjust low and high accordingly.
If target not found, return -1.
This works in O(log n) because each step eliminates half of the search space.

Python Code
class Solution:
def search(self, nums, target):
left = 0
right = len(nums) - 1

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

        if nums[mid] == target:
            return mid

        # Check if left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Output
4