Blind 75 - problem 8 : Search in Rotated Sorted Array

Problem Statement

Search in Rotated Sorted Array

You are given an integer array nums sorted in ascending order and an integer target. Suppose nums is rotated at some pivot unknown to you before you were given the array. For example, [0, 1, 2, 4, 5, 6, 7] might be rotated to [4, 5, 6, 7, 0, 1, 2].

You need to find the index of the target element in the rotated array. If the target does not exist in the array, return -1.

Example:

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

---

Optimal Approach

The most efficient way to solve this problem is by utilizing a modified binary search. The key observation is that at least one half of the array will always be sorted, which means we can determine whether the target lies in the sorted part and then decide which half to search in.

Steps for the optimal approach:

1. Initialize pointers: Start with two pointers, left = 0 and right = n - 1, where n is the size of the array.
2. Binary Search: In each iteration, calculate the middle index mid = left + (right - left) / 2.
3. Identify the sorted half:
   • If nums[mid] is greater than nums[left], then the left half is sorted.
   • Otherwise, the right half is sorted.
4. Decide the next search half:
   • If the left half is sorted and the target is in the range [nums[left], nums[mid]], move the right pointer to mid - 1.
   • If the right half is sorted and the target is in the range [nums[mid], nums[right]], move the left pointer to mid + 1.
5. If the target is found at nums[mid], return mid. If not, repeat until the left pointer exceeds the right pointer.

---

LeetCode-Compatible Code Implementation

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;
            
            // Check if target is found at mid
            if (nums[mid] == target) return mid;
            
            // Left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;  // target lies in the left half
                } else {
                    left = mid + 1;   // target lies in the right half
                }
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;  // target lies in the right half
                } else {
                    right = mid - 1; // target lies in the left half
                }
            }
        }
        
        return -1;  // target not found
    }
};

---

Step-by-Step Explanation of Code

1. Initialization: We initialize the left pointer to 0 and the right pointer to the last index of the array.

2. Binary Search Loop:

   • We calculate the middle index mid using the formula mid = left + (right - left) / 2.
   • If the element at mid is equal to the target, we return mid.

3. Check Sorted Half:

   • If the left part of the array (nums[left] to nums[mid]) is sorted (nums[left] <= nums[mid]), we check if the target lies within this range. If it does, we narrow the search to the left half by setting right = mid - 1; otherwise, we search in the right half.
   • If the right part of the array (nums[mid] to nums[right]) is sorted (nums[mid] < nums[right]), we check if the target lies within this range. If it does, we narrow the search to the right half by setting left = mid + 1; otherwise, we search in the left half.

4. Repeat: The process continues until the left pointer exceeds the right pointer, at which point the target is not found, and we return -1.

---

Dry Run / Execution Steps

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

1. First iteration:

   • left = 0, right = 6
   • mid = 3, nums[mid] = 7
   • Left part is sorted (nums[left] = 4 <= 7 = nums[mid]), but the target is not in this range, so we move to the right half by setting left = 4.

2. Second iteration:

   • left = 4, right = 6
   • mid = 5, nums[mid] = 1
   • Right part is sorted (nums[mid] = 1 < 2 = nums[right]), and the target lies within this range (0 <= target <= 1), so we move to the left half by setting right = 4.

3. Third iteration:

   • left = 4, right = 4
   • mid = 4, nums[mid] = 0
   • We find that nums[mid] == target, so we return 4.

Output:
4

---

Alternative Approaches & Why Not?

1. Brute Force:

   • Traverse the entire array and check if each element equals the target.
   • Time Complexity: O(n)
   • Space Complexity: O(1)
   • This approach is inefficient compared to binary search and is not recommended.

2. Sorting:

   • Sort the array and then apply binary search.
   • Time Complexity: O(n log n) for sorting, plus O(log n) for binary search.
   • Space Complexity: O(n) for sorting (depending on the algorithm used).
   • Sorting is unnecessary since the array is rotated and partially sorted.

3. Two Pointers:

   • This approach would require scanning the array in both directions, which is inefficient.
   • Time Complexity: O(n)
   • Space Complexity: O(1)

---

Best Solution & Why It’s Best

The binary search approach is the most efficient solution for this problem.

Approach	Time Complexity	Space Complexity
Brute Force	O(n)	O(1)
Sorting + BS	O(n log n)	O(n)
Binary Search	O(log n)	O(1)

Explanation:
The binary search approach has the best time complexity of O(log n) and a constant space complexity O(1). This makes it the most optimal solution.

---

Complexity Analysis

• Time Complexity:

  • For each iteration of the binary search, we reduce the search space by half, making the time complexity O(log n).

• Space Complexity:

  • We are using only a few pointers and variables, so the space complexity is O(1).

---

Conclusion

The binary search approach is the most efficient solution for this problem, offering the best time and space complexity. By utilizing the properties of the rotated sorted array, we can quickly locate the target using O(log n) time.

Suggested Problems for Practice:

• Find Peak Element
• Search in Rotated Sorted Array II
• Find Minimum in Rotated Sorted Array