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

    }
}