# Find Minimum in Rotated Sorted Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array)
Canonical: https://scaleengineer.com/dsa/problems/find-minimum-in-rotated-sorted-array
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [FreshWorks](https://scaleengineer.com/companies/freshworks), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Nutanix](https://scaleengineer.com/companies/nutanix), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [eBay](https://scaleengineer.com/companies/ebay), [Tesla](https://scaleengineer.com/companies/tesla), [Synopsys](https://scaleengineer.com/companies/synopsys)
---
## Problem
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 1:**

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

**Example 2:**

**Input:** nums = [4,5,6,7,0,1,2]
**Output:** 0
**Explanation:** The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

**Example 3:**

**Input:** nums = [11,13,15,17]
**Output:** 11
**Explanation:** The original array was [11,13,15,17] and it was rotated 4 times. 

**Constraints:**

* `n == nums.length`
* `1 <= n <= 5000`
* `-5000 <= nums[i] <= 5000`
* All the integers of `nums` are **unique**.
* `nums` is sorted and rotated between `1` and `n` times.

# Approaches
## Linear Scan
This is a straightforward brute-force approach. We can find the minimum element by simply iterating through the entire array and keeping track of the smallest value encountered.
**Time:** O(n) · **Space:** O(1)
**Pros:** Very simple to understand and implement.; It is guaranteed to find the minimum element for any array of numbers, not just rotated sorted ones.
**Cons:** This approach is inefficient and does not meet the O(log n) time complexity requirement specified in the problem description.; It fails to utilize the key property of the input, which is that the array is a rotated version of a sorted array.
### Explanation
The algorithm initializes a variable, say `min_element`, with the value of the first element in the array. It then iterates through the rest of the array from the second element to the last. In each iteration, it compares the current element with `min_element`. If the current element is smaller than `min_element`, `min_element` is updated to the value of the current element. After the loop completes, `min_element` will hold the minimum value in the array. This approach is simple but overlooks the sorted and rotated nature of the array, leading to a suboptimal time complexity.

```java
class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            // This case is ruled out by constraints but good practice.
            throw new IllegalArgumentException("Input array is empty or null.");
        }
        
        int minElement = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < minElement) {
                minElement = nums[i];
            }
        }
        return minElement;
    }
}
```
### Algorithm
- Initialize a variable `min_element` to the first element of the array, `nums[0]`.
- Iterate through the array from the second element (`i = 1`) to the end.
- In each iteration, compare the current element `nums[i]` with `min_element`.
- If `nums[i]` is smaller, update `min_element` to `nums[i]`.
- After the loop finishes, `min_element` will hold the smallest value in the array.

## Binary Search
A much more efficient approach is to use a modified binary search. The key idea is to leverage the property that the array consists of two sorted portions. The minimum element is the first element of the second sorted portion, which is the pivot point where the rotation occurs. Binary search helps us find this pivot point in logarithmic time.
**Time:** O(log n) · **Space:** O(1)
**Pros:** Highly efficient, with a time complexity of O(log n), which meets the problem's requirement.; This is the optimal solution for this problem as it effectively uses the array's properties.
**Cons:** The logic is more complex than a simple linear scan.; Care must be taken with the boundary conditions and pointer updates to avoid infinite loops or incorrect results.
### Explanation
The core of this approach is to determine which half of the current search space contains the minimum element. We use two pointers, `left` and `right`, to define the search space.

First, we can handle the edge case where the array is not rotated at all (or rotated `n` times). If `nums[left] <= nums[right]`, the array segment is sorted in the conventional way, and the minimum element is simply `nums[left]`.

In the main loop, we calculate the middle index `mid`. The decision to shrink the search space is based on comparing `nums[mid]` with an element at one of the boundaries, for instance, `nums[right]`.
- If `nums[mid] > nums[right]`, it implies that the segment from `left` to `mid` is part of the larger-valued, first sorted portion, and the pivot (the minimum element) must lie in the right half (`mid + 1` to `right`). So, we update `left = mid + 1`.
- If `nums[mid] <= nums[right]`, it implies that the segment from `mid` to `right` is the second sorted portion (containing smaller values). The minimum element is either `nums[mid]` itself or somewhere to its left. Therefore, we can safely discard the right part of the search space by updating `right = mid`. We cannot use `right = mid - 1` because `mid` could be the minimum element.

The loop continues until `left` and `right` converge (`left == right`). The element at this index is the minimum element in the rotated array.

```java
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        // The loop invariant is that the minimum element is within [left, right].
        while (left < right) {
            // If the current search space is sorted, the first element is the minimum.
            if (nums[left] < nums[right]) {
                return nums[left];
            }

            int mid = left + (right - left) / 2;

            // If nums[mid] is greater than nums[right], the pivot is in the right half.
            // For example: [4, 5, 6, 7, 0, 1, 2]. mid=7, right=2. 7 > 2. Search [0, 1, 2].
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                // Otherwise, the pivot is in the left half (including mid).
                // For example: [6, 7, 0, 1, 2, 4, 5]. mid=1, right=5. 1 < 5. Search [6, 7, 0, 1].
                right = mid;
            }
        }
        
        // When the loop ends, left == right, pointing to the minimum element.
        return nums[left];
    }
}
```
### Algorithm
- Initialize two pointers, `left = 0` and `right = nums.length - 1`.
- Check if the array is not rotated (or rotated `n` times). If `nums[left] <= nums[right]`, the array is already sorted, so return `nums[left]`.
- Enter a `while` loop that continues as long as `left < right`.
- Calculate the middle index: `mid = left + (right - left) / 2`.
- Compare `nums[mid]` with `nums[right]`. If `nums[mid] > nums[right]`, it means the pivot point (the minimum element) must be in the right half of the current search space. So, we discard the left half by setting `left = mid + 1`.
- Otherwise (`nums[mid] <= nums[right]`), the minimum element is either `nums[mid]` or in the left half. So, we discard the right half by setting `right = mid`.
- The loop terminates when `left` and `right` converge to the same index. This index holds the minimum element. Return `nums[left]`.

# Solutions
### Java

```java
class Solution { public int findMin ( int [] nums ) { int n = nums . length ; if ( nums [ 0 ] <= nums [ n - 1 ]) { return nums [ 0 ]; } int left = 0 , right = n - 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( nums [ 0 ] <= nums [ mid ]) { left = mid + 1 ; } else { right = mid ; } } return nums [ left ]; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var findMin = function (
  nums,
) {
  const n = nums.length;
  if (nums[0] <= nums[n - 1]) {
    return nums[0];
  }
  let left = 0,
    right = n - 1;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[0] <= nums[mid]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
};

```

### CPP

```cpp
class Solution { public: int findMin ( vector < int >& nums ) { int n = nums . size (); if ( nums [ 0 ] <= nums [ n - 1 ]) return nums [ 0 ]; int left = 0 , right = n - 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( nums [ 0 ] <= nums [ mid ]) left = mid + 1 ; else right = mid ; } return nums [ left ]; } };
```

### Python

```python
class Solution : def findMin ( self , nums : List [ int ]) -> int : if nums [ 0 ] <= nums [ - 1 ]: return nums [ 0 ] left , right = 0 , len ( nums ) - 1 while left < right : mid = ( left + right ) >> 1 if nums [ 0 ] <= nums [ mid ]: left = mid + 1 else : right = mid return nums [ left ]
```