Find Minimum in Rotated Sorted Array

lc 153

minimum 拿着end 作为target，然后比较，找最大值，拿着start座位target，然后比较

没有重复元素

 public int findMin(int[] num) {
        // write your code here
        if(num == null || num.length ==0){
            return 0;
        }

        int start = 0;
        int end = num.length - 1;
        int target = num[end];

        while(start + 1 < end){
            int mid = start + (end - start)/2;
            if(num[mid] < target){
                end = mid;
            }else{
                start = mid;
            }    
        }

        if(num[start] < num[end]){
            return num[start];
        }else{
            return num[end];
        }
    }

lc 154

Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

o(n) iterate the array and find the minimums.

    //  这道题目在面试中不会让写完整的程序
    //  只需要知道最坏情况下 [1,1,1....,1] 里有一个
    //  这种情况使得时间复杂度必须是 O(n)
    //  因此写一个for循环就好了。
    //  如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。
    //  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。

// version 1: just for loop is enough
public class Solution {
    public int findMin(int[] num) {
        //  这道题目在面试中不会让写完整的程序
        //  只需要知道最坏情况下 [1,1,1....,1] 里有一个0
        //  这种情况使得时间复杂度必须是 O(n)
        //  因此写一个for循环就好了。
        //  如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。
        //  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。
        int min = num[0];
        for (int i = 1; i < num.length; i++) {
            if (num[i] < min)
                min = num[i];
        }
        return min;
    }
}

// version 2: use *fake* binary-search
public class Solution {
    /**
     * @param num: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == nums[end]) {
                // if mid equals to end, that means it's fine to remove end
                // the smallest element won't be removed
                end--;
            } else if (nums[mid] < nums[end]) {
                end = mid;
                // of course you can merge == & <
            } else {
                start = mid;
                // or start = mid + 1
            }
        }

        if (nums[start] <= nums[end]) {
            return nums[start];
        }
        return nums[end];
    }
}