This page explains Java solution to problem Find Minimum in Rotated Sorted Array II
using Binary Search
algorithm.
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:Example 2:Input: [1,3,5]
Output: 1
Input: [2,2,2,0,1]
Output: 0
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];
}
}
O(log N) Where
N is total number of elements in an input array.
O(1)