154. Find Minimum in Rotated Sorted Array II
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
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
Note:
- This is a follow up problem to Find Minimum in Rotated Sorted Array.
- Would allow duplicates affect the run-time complexity? How and why?
----
Intuition
Standard binary search with unknown target
while (lo <= hi)
when lo == hi => infinite loop => terminate
Need to determine where pivot (minimum element) is relative to mid
if (nums[mid] < nums[hi])
=> mid to hi is strictly increasing
=> search in lower half
=> mid is min, potential ans, cannot discard
=> hi = mid
else if (nums[mid] > nums[hi])
=> pivot is somewhere between mid and hi
=> mid is higher element, discard it
=> lo = mid + 1
else
=> nums[mid] == nums[hi]
=> shrink search space, discarding hi still preserves mid as potential ans
=> eg [1, 1], [3, 3, 3, 1, 3]
----
Time - O(log N)
Space - O(1)
---
Related problems
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int findMin(int[] nums) { | |
| if (nums == null || nums.length == 0) { | |
| return -1; | |
| } | |
| int lo = 0, hi = nums.length - 1; | |
| while (lo <= hi) { | |
| int mid = lo + (hi - lo) / 2; | |
| // starts infinite loop => terminate | |
| if (lo == hi) { | |
| return nums[lo]; | |
| } | |
| if (nums[mid] < nums[hi]) { | |
| // strictly increasing between mid, and hi | |
| // search lower half, cannot discard mid since it is lesser value, potential answer | |
| hi = mid; | |
| } else if (nums[mid] > nums[hi]) { | |
| // pivot in upper half, shift search to upper half | |
| // nums[mid] is greater value, dicard mid as it cannot be pivot which should be minimum | |
| lo = mid + 1; | |
| } else { | |
| // nums[mid] == nums[hi] => shrink search in upper half | |
| // discard hi, this still preserves mid as potential ans | |
| // eg., [3,3,3,1,3], [1,1] | |
| hi -= 1; | |
| } | |
| } | |
| return - 1; | |
| } | |
| } |
