EASY TO MEDIUM SOLUTION || 153. Find Minimum in Rotated Sorted Array
# Intuition\n\nThe task is to find the minimum element in a rotated sorted array, which may contain duplicates. The key points to consider are:\n1. **Rotated Sorted Array**: The array is originally sorted but has been rotated at some pivot, meaning that the smallest element is somewhere in the array.\n2. **Handling Duplicates**: Duplicates can complicate the search, as they may obscure the boundaries of sorted portions.\n\n# Approach\n\nThe approach leverages binary search to efficiently locate the minimum element. Here\u2019s a detailed step-by-step breakdown:\n1. **Initialization**: Start with two pointers, low and high, initialized to the first and last indices of the array, respectively.\n2. **Binary Search Loop**: Continue searching while low is less than high:\n   - Calculate mid as low + (high - low) / 2.\n   - **Check for Sorted Portion**: If nums[low] < nums[high], it indicates that the portion from low to high is sorted, and thus the minimum element must be at low. Return nums[low].\n   - **Handle Duplicates**: If nums[low], nums[mid], and nums[high] are equal, increment low and decrement high. This reduces the search space when duplicates are present.\n   - **Determine Sorted Half**:\n      - If the left half (nums[low] to nums[mid]) is sorted (i.e., nums[low] <= nums[mid]), then the minimum must be in the right half. Set low = mid + 1.\n      - If the right half (nums[mid] to nums[high]) is sorted, then the minimum must be in the left half or could be at mid. Set high = mid.\n3. **Return Minimum**: When the loop ends, low will point to the minimum element. Return nums[low]\n\n# Complexity\n- **Time complexity**: The average case time complexity is O(logN) due to binary search. However, in cases with many duplicates, it can degrade to O(N) in the worst case when all elements are duplicates.\n\n- **Space complexity**: The space complexity is O(1) since we are using a constant amount of extra space for variables.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int findMin(vector<int>& nums) {\n        int n = nums.size();\n        if (n == 1) return nums[0];\n\n        int low = 0, high = n - 1;\n\n        while (low < high) {\n            int mid = low + (high - low) / 2;\n\n            // If we find a sorted part\n            if (nums[low] < nums[high]) {\n                return nums[low]; // The smallest element is at \'low\'\n            }\n\n            // Handle duplicates\n            if (nums[low] == nums[mid] && nums[mid] == nums[high]) {\n                low++; \n                high--; // Shrink the search space\n            } \n            else if (nums[low] <= nums[mid]) {\n                // Left side is sorted, so move to the right\n                low = mid + 1;\n            } \n            else {\n                // Right side must be sorted, so move to the left\n                high = mid; // Note: We keep mid here because it could be the minimum\n            }\n        }\n\n        return nums[low]; // At the end of loop, low should point to the minimum\n    }\n};\n\n```
['Array', 'Binary Search', 'C++']