153. Find Minimum in Rotated Sorted Array

153- Find Minimum in Rotated Sorted Array
**Question
Editorial Solution

My Submissions

Total Accepted: 100021
Total Submissions: 270435
Difficulty: Medium

Suppose a sorted array 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.

Hide Company Tags
Microsoft
Hide Tags
Array Binary Search
Hide Similar Problems
(H) Search in Rotated Sorted Array (H) Find Minimum in Rotated Sorted Array II

 public int findMin(int[] nums) {
        /*
        https://discuss.leetcode.com/topic/5170/java-solution-with-binary-search
        The minimum element must satisfy one of two conditions: 1) If rotate, A[min] < A[min - 1]; 2) If not, A[0]. Therefore, we can use binary search: check the middle element, if it is less than previous one, then it is minimum. If not, there are 2 conditions as well: If it is greater than both left and right element, then minimum element should be on its right, otherwise on its left.
        */


  int start = 0, end = nums.length - 1;

  while (start < end) {
   int mid = start + (end - start) / 2;
   if (nums[end] < nums[mid]) {
    start = mid + 1; // 转折点在mid 的右侧
   } else {
    end = mid;
   }
  }
  return nums[start];
  // start == end is the smallest value and also the number of places
  }