> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/binary-search/find-minimum-in-rotated-sorted-array.md).

# 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/>