Find Minimum in Rotated Sorted Array II

This page explains Java solution to problem Find Minimum in Rotated Sorted Array II using Binary Search algorithm.

Problem Statement

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element. The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0


If you have any suggestions in below code, please create a pull request by clicking here.


class FindMinimumInRotatedSortedArrayIi {
    public int findMin(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while(lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if(nums[mid] > nums[hi]) lo = mid + 1;
            else if(nums[mid] < nums[hi]) hi = mid;
            else hi--;
        return nums[lo];

Time Complexity

O(log N) Where
N is total number of elements in an input array.

Space Complexity