# Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`).

Find the minimum element.

You may assume no duplicate exists in the array.

**Example 1:**

```
Input:
 [3,4,5,1,2] 

Output:
 1
```

**Example 2:**

```
Input:
 [4,5,6,7,0,1,2]

Output:
 0
```

## Analysis

Search in Rotated Sorted Array变形。基本思想还是利用Binary Search，但是在如何移动左右boundary时要相应调整。

```
  /
 /
/
____
   /
  /
```

不论用Template #1，#2，#3，本质都是在寻找一个非单调递增区间，这个区间就包含了最小值。

Source: <https://leetcode.com/articles/find-minimum-in-rotated-sorted-array/>

If the array is not rotated and the array is in ascending order, then `last element > first element`.

*Inflection Point*

> All the elements to the left of inflection point > first element of the array.
>
> All the elements to the right of inflection point < first element of the array.

**Template #1 Algorithm**

1. Find the`mid`element of the array.
2. If`mid element > first element of array`this means that we need to look for the inflection point on the right of`mid`.
3. If`mid element < first element of array`this that we need to look for the inflection point on the left of`mid`.
4. We stop our search when we find the inflection point, when either of the two conditions is satisfied:
   1. `nums[mid] > nums[mid + 1]`Hence, **mid+1** is the smallest.
   2. `nums[mid - 1] > nums[mid]`Hence, **mid** is the smallest.

## Solution

Using Template #1

```java
class Solution {
  public int findMin(int[] nums) {
    // If the list has just one element then return that element.
    if (nums.length == 1) {
      return nums[0];
    }

    // initializing left and right pointers.
    int left = 0, right = nums.length - 1;

    // if the last element is greater than the first element then there is no rotation.
    // e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
    // Hence the smallest element is first element. A[0]
    if (nums[right] > nums[0]) {
      return nums[0];
    }

    // Binary search way
    while (right >= left) {
      // Find the mid element
      int mid = left + (right - left) / 2;

      // if the mid element is greater than its next element then mid+1 element is the smallest
      // This point would be the point of change. From higher to lower value.
      if (nums[mid] > nums[mid + 1]) {
        return nums[mid + 1];
      }

      // if the mid element is lesser than its previous element then mid element is the smallest
      if (nums[mid - 1] > nums[mid]) {
        return nums[mid];
      }

      // if the mid elements value is greater than the 0th element this means
      // the least value is still somewhere to the right as we are still dealing with elements
      // greater than nums[0]
      if (nums[mid] > nums[0]) {
        left = mid + 1;
      } else {
        // if nums[0] is greater than the mid value then this means the smallest value is somewhere to
        // the left
        right = mid - 1;
      }
    }
    return -1;
  }
}
```

Using BS Template #3

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

Using Template #2

```java
class Solution {
    public int findMin(int[] nums) {
        int i=0,j=nums.length-1;
        while(i<j)
        {
            int mid=i+(j-i)/2;
            if(nums[mid]<nums[j])
                j=mid;
            else
                i=mid+1;
        }
        return nums[i];
    }
}
```

## Reference

<https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/solution/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/binary-search/find-minimum-in-rotated-sorted-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.