Find Minimum in Rotated Sorted Array

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 of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

public int findMin(int[] nums) {
    int start = 0, end = nums.length-1;
    while(start < end){
        int mid = start + (end - start) / 2;
        if(nums[end] < nums[mid]){
            start = mid + 1;
        }else{
            end = mid;
        }
    }
    return nums[start];
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let start = 0;
  let end = nums.length - 1;
  while (start < end) {
    let mid = Math.floor(start + (end - start) / 2);
    if (nums[end] < nums[mid]) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }
  return nums[start];
};

class Solution:
    def findMin(self, nums: List[int]) -> int:
        start = 0
        end = len(nums) - 1
        while start < end:
            mid = start + (end - start) // 2
            if nums[end] < nums[mid]:
                start = mid + 1
            else:
                end = mid
        return nums[start]

class Solution {
public:
    int findMin(vector<int>& nums) {
        int start = 0;
        int end = nums.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[end] < nums[mid]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return nums[start];
    }
};

Time/Space Complexity:

Time Complexity: O(logn)
Space Complexity: O(1)

Explanation:

Modified binary search and the best way to explain it might be with examples:

[2, 3, 4, 5, 1] we have mid element larger than start in that case we know left side is totally ordered and we check if element at mid is smaller than element at end, if it is we can discard the right side and only search in left side, if it's not it means that we have to search the right side
[5, 1, 2, 3, 4] in this example by checking if nums[mid] > nums[start] we get 2 < 5 so we know the right side is still in total order and we can check if the element at end is larger than element at min in non-rotated part, if it is that we know smallest number is either at mid or in the left side. If element at mid was larger than the element at end we would discard the element at mid at search the right side start = mid+1

Java
JavaScript
Python
C++

public int findMin(int[] nums) {
    int start = 0, end = nums.length-1;
    while(start < end){
        int mid = start + (end - start) / 2;
        if(nums[mid] > nums[start]){
            if(nums[end] > nums[mid]){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }else{
            if(nums[end] > nums[mid]){
                end = mid;
            }else{
                start = mid + 1;
            }
        }
    }
    return nums[start];
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let start = 0;
  let end = nums.length - 1;
  while (start < end) {
    let mid = start + Math.floor((end - start) / 2);
    if (nums[mid] > nums[start]) {
      if (nums[end] > nums[mid]) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    } else {
      if (nums[end] > nums[mid]) {
        end = mid;
      } else {
        start = mid + 1;
      }
    }
  }
  return nums[start];
};

class Solution:
    def findMin(self, nums: List[int]) -> int:
        start = 0
        end = len(nums) - 1
        while start < end:
            mid = start + (end - start) // 2
            if nums[mid] > nums[start]:
                if nums[end] > nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                if nums[end] > nums[mid]:
                    end = mid
                else:
                    start = mid + 1
        return nums[start]

class Solution {
public:
    int findMin(vector<int>& nums) {
        int start = 0;
        int end = nums.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > nums[start]) {
                if (nums[end] > nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (nums[end] > nums[mid]) {
                    end = mid;
                } else {
                    start = mid + 1;
                }
            }
        }
        return nums[start];
    }
};

Now note that some scenarios aren't possible since the array was initially sorted, if we have:

nums[end] < nums[mid] that means that right side is not totally ordered and in the right side we will find our minimum number
nums[end] > nums[mid] which also implies nums[mid] < nums[start] our right side is totally ordered, and the solution is either the element at mid or some element in the left side.

Using the above two points we can simplify the solution to:

Java
JavaScript
Python
C++

public int findMin(int[] nums) {
    int start = 0, end = nums.length-1;
    while(start < end){
        int mid = start + (end - start) / 2;
        if(nums[end] < nums[mid]){
            start = mid + 1;
        }else{
            end = mid;
        }
    }
    return nums[start];
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let start = 0;
  let end = nums.length - 1;
  while (start < end) {
    let mid = Math.floor(start + (end - start) / 2);
    if (nums[end] < nums[mid]) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }
  return nums[start];
};

class Solution:
    def findMin(self, nums: List[int]) -> int:
        start = 0
        end = len(nums) - 1
        while start < end:
            mid = start + (end - start) // 2
            if nums[end] < nums[mid]:
                start = mid + 1
            else:
                end = mid
        return nums[start]

class Solution {
public:
    int findMin(vector<int>& nums) {
        int start = 0;
        int end = nums.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[end] < nums[mid]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return nums[start];
    }
};

Example 1:​

Example 2:​

Example 3:​

Constraints:​

Solution:​

Time/Space Complexity:​

Explanation:​