153. Find Minimum in Rotated Sorted Array

📝 Problem Details

• Title: 153. Find Minimum in Rotated Sorted Array
• Link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
• Difficulty: Medium
• Tags/Categories: Binary-Search

💭What Were My Initial Thoughts?

- the array is sorted but rotated, meaning there exists a pivot point where the sorted order is disrupted
- binary search is ideal since we can determine which half to search in based on the values at mid and right

💡 Explanation of Solution

use binary search, moving the left and right pointers under the following conditions:

- case 1: if nums[mid] > nums[right], it means the min is in the right half (since mid is still in the rotated part)

- case 2: if nums[mid] < nums[right], it means the min is in the left half (or is the mid position itself)

⌛ Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
 
        while(left < right) {
            int mid = left + (right - left) / 2;
 
            if(nums[mid] > nums[right]) {
                left = mid + 1; // min must be in right half
            }
            else {
                right = mid; // mind could be at mid or in the left half
            }            
        }
        return nums[left]; // when left == right, we found the minimum 
    }
};