154. Find Minimum in Rotated Sorted Array II

Source link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

Design

The problem could be solved by the binary search approach. The key process is shown as below:

  1. If the array on the right side of the middle point is unsorted, drop the left part.
  2. If the array on the right side of the middle point is sorted, drop the right part.
  3. If the middle point equals to the element where the right pointer at, represent duplicates occur, drop the duplicate element.

Implementation

class Solution {
  public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid = left + (right - left) / 2;
      // If the right side of mid is unsorted
      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else if (nums[mid] < nums[right]) { // If the right side of mid is sorted
        right = mid;
      } else { // If nums[mid] = nums[right], drop the duplicate
        right--;
      }
    }
    return nums[left];
  }
}

Complexity Analysis

Time: $O(logn)$

Space: $O(1)$