[LeetCode] 153. Find Minimum in Rotated Sorted Array

Posted on | In

Problem

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:

1
2
Input: [3,4,5,1,2]
Output: 1

Example 2:

1
2
Input: [4,5,6,7,0,1,2]
Output: 0

Explanation

  1. Check if the array is rotated by comparing first element and last element. If the array is not ratated, then return the first element.

  2. We can use binary search to solve this problem. Create a left and right pointer that points to beginning index and end index of the array. Then we can get the middle index element nums[mid], and compare it with the right element nums[right].

  3. if nums[mid] is greater than nums[right], then we update left = mid + 1.

    1
    2
    3
    4
    5
    6
    7
    8
             /
    mid /
       /
      /
 left/
           /right
          /
        min

  4. Else if nums[mid] is less than nums[right], then we update right = mid.

    1
    2
    3
    4
    5
    6
    7
    8
    9
          /
     /
 left
           /right
          /
         /
        /mid
       /
     min

  5. Else nums[mid] equal to nums[right], that means left == right since all elements are unique, we break out the while loop and return nums[left].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
        }

        return nums[left];
    }
}