# 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:

- 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.
- 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)$