154. Find Minimum in Rotated Sorted Array II (Contains duplicates) (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.

154. Find Minimum in Rotated Sorted Array II (#1 Binary search + linear search).java

// Binary search solution: min always lies in the rotated half
// Modified from 153: To deal with duplicates, scan through when begin == mid == end
// Note: take care of equal when comparing
// Time: O(n), 0ms
// Space: O(1), 38.2mb
class Solution {
    public int findMin(int[] nums) {
        // Corner case: 1 element
        if(nums.length == 1) {
            return nums[0];
        }
        
        int begin = 0, end = nums.length - 1;
        while(begin < end - 1) { // At least 3 elements in the range
            int mid = begin + (end - begin) / 2;
            
            if(nums[begin] == nums[mid] && nums[mid] == nums[end]) {
                // If we can't decide which part to go, scan it to find min
                int min = nums[begin];
                for(int i = begin; i <= end; i++) {
                    min = Math.min(min, nums[i]);
                }
                return min;
                
            } else if(nums[begin] <= nums[mid] && nums[mid] <= nums[end]) {
                // If the array is sorted, return the first one
                return nums[begin];
                
            } else if(nums[begin] > nums[mid] && nums[mid] <= nums[end]) {
                // If the first one is rotated, focus on that half
                end = mid; // Always keep the mid in the range because it can be the min
                
            } else { // nums[begin] <= nums[mid] && nums[mid] > nums[end]
                // If the second one is rotated, focus on that half
                begin = mid;
            }
        }
        
        // begin == end - 1, only 2 elements in the range
        return Math.min(nums[begin], nums[end]);
    }
}