Binary Search - Find Minimum in Rotated Sorted Array II (Duplicates)

Same as Find Minimum in Rotated Sorted Array but the array may contain duplicates. Return the minimum element.

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

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

Similar to version I but when nums[mid] == nums[hi] we cannot determine which half contains the minimum, so we decrement hi by 1.

While lo < hi:
If nums[mid] > nums[hi]: lo = mid + 1.
Else if nums[mid] < nums[hi]: hi = mid.
Else (nums[mid] == nums[hi]): hi-- (safely shrink).

class Solution { public int findMin(int[] nums) { int lo = 0, 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(N) worst case (all duplicates), O(log N) average
Space Complexity: O(1)