Search in Rotated Sorted Array - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Find the index of a target value in a sorted array that has been rotated an unknown number of times, or return -1 if not found.
Get the length n of the array nums.
Initialize two pointers, l to 0 and r to n-1, to find the rotation point (minimum element).
While l is less than r, compute the middle index m as (l + r) // 2.
If nums[m] is greater than nums[r], the minimum is in the right half, so set l to m + 1.
Otherwise, the minimum is in the left half including m, so set r to m.
Set min_i to l as the index of the minimum element (rotation point).
Determine the search range based on min_i and target:
If min_i is 0, search the entire array (l = 0, r = n-1).
If target is between nums[0] and nums[min_i-1], search the first part (l = 0, r = min_i-1).
Otherwise, search the second part (l = min_i, r = n-1).
Perform binary search in the determined range:
While l is less than or equal to r, compute m as (l + r) // 2.
If nums[m] equals target, return m.
If nums[m] is less than target, set l to m + 1.
If nums[m] is greater than target, set r to m - 1.
Return -1 if the target is not found.

Code Solution

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l = 0
        r = n - 1

        while l < r:
            m = (l + r) // 2

            if nums[m] > nums[r]:
                l = m + 1
            else:
                r = m

        min_i = l

        if min_i == 0:
            l, r = 0, n - 1
        elif target >= nums[0] and target <= nums[min_i - 1]:
            l, r = 0, min_i - 1
        else:
            l, r = min_i, n - 1

        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            elif nums[m] < target:
                l = m + 1
            else:
                r = m - 1
        return -1

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

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0;
        int r = n - 1;

        while (l < r) {
            int m = (l + r) / 2;

            if (nums[m] > nums[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }

        int minIndex = l;

        if (minIndex == 0) {
            l = 0;
            r = n - 1;
        } else if (target >= nums[0] && target <= nums[minIndex - 1]) {
            l = 0;
            r = minIndex - 1;
        } else {
            l = minIndex;
            r = n - 1;
        }

        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return -1;
    }
};

public class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;

        while (l < r) {
            int m = (l + r) / 2;

            if (nums[m] > nums[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }

        int minIndex = l;

        if (minIndex == 0) {
            l = 0;
            r = n - 1;
        } else if (target >= nums[0] && target <= nums[minIndex - 1]) {
            l = 0;
            r = minIndex - 1;
        } else {
            l = minIndex;
            r = n - 1;
        }

        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return -1;
    }
}

var search = function(nums, target) {
    let n = nums.length;
    let l = 0;
    let r = n - 1;

    while (l < r) {
        let m = Math.floor((l + r) / 2);

        if (nums[m] > nums[r]) {
            l = m + 1;
        } else {
            r = m;
        }
    }

    let minIndex = l;

    if (minIndex === 0) {
        l = 0;
        r = n - 1;
    } else if (target >= nums[0] && target <= nums[minIndex - 1]) {
        l = 0;
        r = minIndex - 1;
    } else {
        l = minIndex;
        r = n - 1;
    }

    while (l <= r) {
        let m = Math.floor((l + r) / 2);
        if (nums[m] === target) {
            return m;
        } else if (nums[m] < target) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    return -1;
};

Detailed Explanation

Understanding the Problem: Search in Rotated Sorted Array

The “Search in Rotated Sorted Array” problem asks us to find the index of a target element in a sorted array that has been rotated at an unknown pivot. If the target exists, return its index; otherwise, return -1.

This array is guaranteed to have been rotated but contains no duplicates. Each half of the array retains a sorted structure, which makes this an ideal case for binary search with modifications.

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

Why This Problem Matters

This problem teaches how to adapt binary search to handle rotations — a common transformation of sorted data in problems involving circular arrays or incomplete sorting. It's frequently asked in technical interviews due to its balance of logic and binary search manipulation.

Optimal Approach: Modified Binary Search

The trick to solving this efficiently is recognizing that at least one half of the array is always sorted. By determining which half is sorted at each step, we can decide where to move the search window.

Steps:

Initialize left = 0 and right = nums.length - 1.
While left <= right:
- Compute mid = Math.floor((left + right) / 2).
- If nums[mid] == target, return mid.
- Determine which half is sorted:
  - If nums[left] <= nums[mid]: the left half is sorted.
  - Check if target is in this range:
    - If nums[left] <= target < nums[mid], search left: right = mid - 1.
    - Otherwise, search right: left = mid + 1.
  - Else: the right half is sorted.
  - Check if target is in this range:
    - If nums[mid] < target <= nums[right], search right: left = mid + 1.
    - Otherwise, search left: right = mid - 1.
If the loop ends, the target does not exist in the array → return -1.

Example Walkthrough

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

left = 0, right = 6 → mid = 3 → nums[3] = 7
Left half [4,5,6,7] is sorted, but 0 is not in this range → search right → left = 4
mid = 5 → nums[5] = 1 → right half [0,1,2] is sorted → 0 is in range → right = 4
mid = 4 → nums[4] = 0 → match found → return 4

Time and Space Complexity

Time Complexity: O(log n), where n is the number of elements in the array. Each iteration cuts the search space in half.
Space Complexity: O(1), as we use only constant extra memory.

Edge Cases to Consider

Array with one element → check directly
Array not rotated at all → standard binary search still works
Target is first or last element → ensure boundaries are handled correctly

Conclusion

The “Search in Rotated Sorted Array” problem is a brilliant example of how binary search can be extended beyond simple sorted arrays. By cleverly identifying the sorted half at each step, we can zero in on the target efficiently, even after the array has been rotated.

Get Personalized Support at AlgoMap Bootcamp 💡