# LeetCode 153. Find Minimum in Rotated Sorted Array

### **Question**

Suppose an array of length `n` sorted in ascending order is **rotated** between `1` and `n` times. For example, the array `nums = [0,1,2,4,5,6,7]` might become:

* `[4,5,6,7,0,1,2]` if it was rotated `4` times.
    
* `[0,1,2,4,5,6,7]` if it was rotated `7` times.
    

Notice that **rotating** an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.

Given the sorted rotated array `nums` of **unique** elements, return *the minimum element of this array*.

You must write an algorithm that runs in `O(log n) time`.

### **Example**

* Input: nums = \[3,4,5,1,2\]
    
* Output: 1
    
* Explanation: The original array was \[1,2,3,4,5\] rotated 3 times.
    

```cpp
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        int mid;

        while (left < right) {
            mid = left + (right - left) / 2;
            
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
            else if (nums[mid] <= nums[right]) {
                right = mid;
            }
        }
        return nums[left];
    }
};
```

### **Problem Summary**

Given a sorted array of a unique elements that has been rotated, find the minimum element in the array. The algorithm must have a time complexity of O(logn).

### **Core Idea**

The key constraints is the O(logn) time complexity, which stongly suggests a Binary Search approach.

Although the entire array is not sorted, it is composed of two sorted subarrays. The minimum element is the “pivot” point where the rotation occurs (i.e., the first element of the second sorted array.)

The strategy is to use binary search to efficiently find this pivot point. We can determine which of the two sorted subarrays our `mid` pointer is in by comparing `nums[mid]` with the element at the right boundary, `nums[right]` .

### **Algorithm Logic**

1. Initialize two pinters: `left = 0` and `right = num.size() - 1` .
    
2. Loop as long as `left < right`.
    
3. Calculate middle index using `left + (right - left) / 2` . This formula is preferred over `(left + right) / 2` to prevent potential integer overflow if the numbers are very large.
    
4. Compare `num[mid]` with `nums[right]` to decide which half of the array to discard:
    
    * If `nums[mid] > nums[right]` : This indicates that the `mid` element is in the larger, left sorted subarray. Therefore, the pivot must be in the right half. We discard the left half by setting `left = mid + 1` .
        
    * If `num[mid] ≤ nums[right]` : This indicates that the segment from `mid` to `right` is sorted. The minimum element must be in the left half, and it’s possible that `nums[mid]` is the minimum itself. We discard the right half by setting `right = mid` .
        
5. The loop terminates when `left` and `right` converge to the same index. This index holds the minimum element in the array.
    
6. Return `nums[left]`
    
7. if nums\[mid\] &gt; nums\[right\], then make the left flag be mid + 1.
    
8. else if nums\[mid\] ≤ nums\[right\], make the right flag be mid.
    

### **Example Walkthrough**

Let's trace the algorithm with `nums = [3, 4, 5, 1, 2]`.

* **Initial State:** `left = 0`, `right = 4`
    
* **Iteration 1:**
    
    * `mid = 0 + (4 - 0) / 2 = 2`
        
    * `nums[mid]` is `nums[2]`, which is `5`.
        
    * `nums[right]` is `nums[4]`, which is `2`.
        
    * Condition `nums[mid] > nums[right]` (5 &gt; 2) is **true**.
        
    * The minimum must be to the right of `mid`. We update `left = mid + 1 = 3`.
        
    * New search space: `[3, 4]` (elements `[1, 2]`).
        
* **Iteration 2:**
    
    * `left = 3`, `right = 4`.
        
    * `mid = 3 + (4 - 3) / 2 = 3`.
        
    * `nums[mid]` is `nums[3]`, which is `1`.
        
    * `nums[right]` is `nums[4]`, which is `2`.
        
    * Condition `nums[mid] > nums[right]` (1 &gt; 2) is **false**. We use the `else` block.
        
    * The minimum is in the left half (or `mid` is the minimum). We update `right = mid = 3`.
        
    * New search space: `[3, 3]` (element `[1]`).
        
* **Termination:**
    
    * Now, `left = 3` and `right = 3`. The `while (left < right)` condition is false. The loop ends.
        
* **Result:**
    
    * Return `nums[left]`, which is `nums[3]`, giving us the answer `1`.