Search in Rotated Sorted Array | Leetcode 33 Solution

Searching for an element in a rotated sorted array is a common coding problem that can appear in technical interviews. It combines concepts of array manipulation and binary search, making it an essential topic to master. In this blog post, we will explore solutions for Search in Rotated Sorted Array from naive to optimal, providing Java implementations for each.

Problem Statement for Search in Rotated Sorted Array

You are given a rotated sorted array and a target value. Your task is to find the index of the target in the array. If the target is not found, return -1.

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

Constraints:

1. The array is sorted in ascending order and then rotated.
2. All elements are unique.
3. The array does not contain duplicates.

Naive Solution for Search in Rotated Sorted Array

The simplest way to solve this problem is to iterate through the array and compare each element with the target. This approach has a time complexity of O(n).

Java Implementation:

public int searchNaive(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

Complexity Analysis:

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

Improved Solution: Binary Search Without Considering Rotation

If the array were not rotated, we could use a standard binary search algorithm. Ignoring the rotation for now, let’s use binary search on the array.

Java Implementation:

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

    return -1;
}

Complexity Analysis:

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

However, this solution works only for a non-rotated array. Let’s address the rotation next.

Optimal Solution: Binary Search with Rotation Handling

To handle the rotation, we need to modify the binary search. The key insight is that one half of the array will always be sorted.

Steps:

1. Identify which half of the array is sorted.
2. Check if the target lies within the sorted half.
3. Adjust the search space accordingly.

Java Implementation:

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;
        }

        // Check if the 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;
}

Complexity Analysis:

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

Conclusion

We have explored multiple solutions for the Leetcode 33- “Search in Rotated Sorted Array” problem, starting from a naive linear search to an optimal binary search that accounts for rotation. The optimal solution achieves a time complexity of O(log n) and is the most efficient approach.

Summary of Approaches:

Understanding and implementing these techniques will strengthen your problem-solving skills for similar coding challenges.