# 153. Find Minimum in Rotated Sorted Array

## Problem

{% embed url="<https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/>" %}

## Intuition

{% hint style="info" %}
Array is sorted in non decreasing order
{% endhint %}

At every iteration, we need to eliminate half the entries. That's the basic of binary search.&#x20;

Here we do not have any specified target to search for, we need to find minimum values in **ROTATED SORTED ARRAY.**

We will perform normal binary search, and at every iteration we will check if the sub array we have gotten from `low` to `mid` is left sorted or right sorted.

* If the sub array is left sorted, minimum will always be on `low`
* If the sub array is right sorted, minimum will always be on `mid`

## Time Complexity

`O(log n)`

## Space Complexity

`O(n)`

## Solution

```java
class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length -1;

        int min = Integer.MAX_VALUE;

        while(low <= high) {
            int mid = low + (high - low)/2;

            if(nums[low] <= nums[mid]) { // Left sorted
                // If left sorted, min number in left subarray will be on low
                min = Math.min(min, nums[low]); 
                low = mid + 1;
            } else { // Right sorted
                // If right sorted, min number in right subarray will be on mid
                min = Math.min(min, nums[mid]);
                high = mid - 1;
            }
        }
        return min;
    }
}
```