Search in Rotated Sorted Array

medium Binary Search

You are given a sorted array of distinct integers that has been rotated at some unknown pivot index. For example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Given the rotated array nums and an integer target, return the index of target if it exists, or -1 otherwise. Your algorithm must run in O(log n) time.

Example

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

Output: 4

The original sorted array [0, 1, 2, 4, 5, 6, 7] was rotated at the pivot, becoming [4, 5, 6, 7, 0, 1, 2]. The target value 0 is at index 4.

Use binary search but first determine which half of the array is sorted. If the target falls within the sorted half's range, search there; otherwise search the other half. This lets you eliminate half the array each step even though it's rotated.

Why this works

In a rotated sorted array, at least one half (left or right of mid) is always properly sorted. You can check if the target falls within the sorted half’s range. If it does, search there; otherwise, search the other half. This preserves the O(log n) binary search guarantee.

Step by step

Find the midpoint — standard binary search: check if nums[mid] is the target.
Determine which half is sorted — if nums[left] <= nums[mid], the left half is in order; otherwise the right half is.
Check if target is in the sorted half — use simple range comparison since that half is properly sorted.
Eliminate one half — move left or right to discard the half that can’t contain the target.

Time: O(log n) Space: O(1)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {  // left half is sorted
                if (nums[left] <= target && target < nums[mid]) {  // target is in the sorted left half
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {  // right half is sorted
                if (nums[mid] < target && target <= nums[right]) {  // target is in the sorted right half
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {  // left half is sorted
                if (nums[left] <= target && target < nums[mid]) {  // target is in the sorted left half
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {  // right half is sorted
                if (nums[mid] < target && target <= nums[right]) {  // target is in the sorted right half
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

def search(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
        if nums[left] <= nums[mid]:  # left half is sorted
            if nums[left] <= target < nums[mid]:  # target is in the sorted left half
                right = mid - 1
            else:
                left = mid + 1
        else:  # right half is sorted
            if nums[mid] < target <= nums[right]:  # target is in the sorted right half
                left = mid + 1
            else:
                right = mid - 1
    return -1