class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 1) return nums[0]; // [1]
        
        // n <= 5000 = 5 * 10^3 --> O(n^2)
        
        int i_left = 0;
        int i_right = nums.length - 1;
        
        while (true) {
            if (i_left > i_right) break;
            
            int i_mid = (i_left + i_right) / 2;
            
            // find the gap 
            int i_mid_next = (i_mid + 1) % nums.length;
            if (nums[i_mid] > nums[i_mid_next]) {
                // found the gap
                return nums[i_mid_next]; // return the smallest number 
            }
            
            int i_mid_prev = ((i_mid - 1) + nums.length) % nums.length; 
            if (nums[i_mid_prev] > nums[i_mid]) {
                // found the gap
                return nums[i_mid];
            }
            
            if (nums[i_mid] > nums[i_left]) {
                // going up trend - the gap is at the right side 
                i_left = i_mid + 1;
            }else if (nums[i_mid] < nums[i_left]) {
                // going down trend - the gap is at the left side 
                i_right = i_mid - 1;
            }else if (nums[i_mid] == nums[i_left]) {
                // this is like going up trend, too 
                i_left = i_mid + 1; // attention: be sure to cover all cases 
            }
            
        }
        
        return -999; // should not reach here 
        
    }
}