153. Find Minimum in Rotated Sorted Array

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

Design

The problem could be solved by the binary search pattern, which the key process is shown as below:

  1. If the middle point is smaller than its previous element, which represents that the pivot point is found. E.g. [3, 4, 5, 6, 1, 2] → the minimum is 1, and it is smaller than its previous value.
  2. If the array is sorted on the left side of the middle point and is unsorted on its right, drop the left part of the array. E.g. [3, 4, 5, 6, 1, 2] → the middle point is 5, and the array is sorted on its left, and is unsorted on the right. Otherwise, drop the right part of the array.

Implementation

class Solution {
  public int findMin(int[] nums) {
    if (nums == null || nums.length == 0) return 0;

    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (mid > 0 && nums[mid] < nums[mid - 1]) { // e.g. [3, 4, 5, 6, 1, 2] -> 1 is smaller than 6
        return nums[mid];
        // If it is sorted on the left side and unsorted on the right side, it can be either one of these both condition, but we write both
      } else if (nums[mid] >= nums[left] && nums[mid] > nums[right]) {
        // e.g. [3, 4, 5, 6, 1, 2] -> mid is 5, it is sorted on its left side and is unsorted on its rightside
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return nums[left];
  }
}

Complexity Analysis

Time: $O(logn)$

Space: $O(1)$