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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

 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
  }