Search in Rotated Sorted Array - Practice Coding Problems

Search in Rotated Sorted Array - Problem

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).

For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Input & Output

Example 1 — Target Found

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

› Output: 4

💡 Note: The array was rotated at index 4. Target 0 is found at index 4.

Example 2 — Target Not Found

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

› Output: -1

💡 Note: Target 3 does not exist in the array, so return -1.

Example 3 — Single Element

$ Input: nums = [1], target = 0

› Output: -1

💡 Note: Single element array where target is not found.

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
All values of nums are unique
nums is an ascending array that is possibly rotated
-10⁴ ≤ target ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Original

Sorted array [0,1,2,4,5,6,7]

Rotated

After rotation: [4,5,6,7,0,1,2]

Find target using binary search

Key Takeaway

🎯 Key Insight: In a rotated sorted array, at least one half is always properly sorted, enabling efficient binary search

Asked in

A Amazon 45 G Google 38 M Microsoft 32 F Facebook 28

The key insight is that in any rotated sorted array, at least one half is always properly sorted. We can use modified binary search to determine which half is sorted and whether our target lies within that sorted range. Best approach uses binary search: Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Modified Binary Search	O(log n)	O(1)	Use binary search by determining which half is sorted at each step
Linear Search	O(n)	O(1)	Scan through the array from left to right to find the target

Modified Binary Search — Algorithm Steps

Set left and right pointers
Find middle element
Determine which half is properly sorted
Check if target is in the sorted half
Move to appropriate half and repeat

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set left=0, right=6, mid=3

Check Sorted Half

Left half [4,5,6,7] is sorted, target 0 not in range

Search Right

Move to right half and find target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        }
        
        // Check if left half is sorted
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(nums, numsSize, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Binary search eliminates half the search space in each iteration

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for pointers

✓ Linear Space

89.4K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Modified Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler