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 themidelement of the array.

2. Ifmid element > first element of arraythis means that we need to look for the inflection point on the right ofmid.

3. Ifmid element < first element of arraythis that we need to look for the inflection point on the left ofmid.

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/