> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/search/153.-find-minimum-in-rotated-sorted-array.md).

# 153. Find Minimum in Rotated Sorted Array

Suppose an array of length `n` sorted in ascending order is **rotated** between `1` and `n` times. For example, the array `nums = [0,1,2,4,5,6,7]` might become:

* `[4,5,6,7,0,1,2]` if it was rotated `4` times.
* `[0,1,2,4,5,6,7]` if it was rotated `7` times.

Notice that **rotating** an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.

[Given the sorted rotated array `nums`, return *the minimum element of this array*.](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)

recursion

```java
class Solution {
    public int findMin(int[] nums) {
        // if array is rotated, the first element will always larger than the last elememt
        // binary search
        return binarySearch(nums, 0, nums.length);
    }
    
    private int binarySearch(int[] nums, int start, int end){
        //end is the not searchaable
        int mid = (start+end)/2;
        if (mid==0 || mid==nums.length || nums[mid-1]>nums[mid]) return nums[mid%nums.length];
        if (nums[mid]>nums[0]) return binarySearch(nums, mid+1, end);
        else return binarySearch(nums, start, mid);   
    }
}
```

iterative

```java
class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        
// end not inculdded
        int end = nums.length;
        while (start<end){
            int mid = (start+end)/2;
            if (mid == 0 || nums[mid-1]>nums[mid]) return nums[mid];
            if (nums[mid]>nums[0]) start=mid+1;
            else end=mid;        
        }
        
        return nums[0];
    }
}
```

```java
class Solution {
    public int findMin(int[] nums) {
        int start =0;
        // include the last element
        int end = nums.length-1;
        while(start<=end){
            int mid = (start+end)/2;
            if (mid>0 && nums[mid-1]>nums[mid]) return nums[mid];
            if (nums[mid]>=nums[0]) start=mid+1;
            else end = mid;
        }
        
        return nums[0];
    }
}
```