# 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时要相应调整。

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

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

``````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

``````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

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