[153. Find Minimum in Rotated Sorted Array] #leetcode

153_0928.java

class Solution {
  // O(n) 
    public int findMin(int[] nums) {
        int res = nums[0];
        for (int n : nums) {
            if (n >= res) {
                res = n;
            } else {
                return n;
            }
        }
        return nums[0];
    }
}


class Solution {
  // O(lg(n))
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        int left = 0, right = nums.length-1;
        
        while (left < right) {
            if (nums[left] < nums[right]) {
                return nums[left];
            } 
            
            int mid = (left + right) / 2;
            
            if (nums[mid] >= nums[left] && nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
            
        }
        
        return nums[left];
    }
}