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.

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

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

Solution

package com.vc.hard;

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

O(1)