Search in Rotated Sorted Array

Problem Statement

An ascending sorted array of distinct values is rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] becomes [4,5,6,7,0,1,2]). Given nums and a target, return its index or -1, in O(log n).

Example

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

Approach

At each step one half of the window is always sorted. Compare nums[left] with nums[mid]: if nums[left] <= nums[mid] the left half is sorted, otherwise the right half is. Check whether the target lies inside the sorted half; if so search there, else search the other half.

Complexity

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

Solution Code

Python

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

Java

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]) {
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

C++

int search(vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

Key Takeaways

• Exactly one side of mid is always sorted — use that to decide where to go.
• Boundary comparisons use <= carefully to include endpoints.
• Reference: LeetCode 33 (Search in Rotated Sorted Array).