153. Find Minimum in Rotated Sorted Array

Problem:

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.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

Analysis:
6/19/2018 update:
This problem finds minimum, so we can apply start + 1 < end template, since there is a standard, minimum, to check.
-------------------------------------------------------------------------------------------------------------------------
01/18/2018 update
Template 1 solution:

class Solution {
    public int findMin(int[] nums) {
        int start = 0, end = nums.length - 1;
        while (start+ 1< end) {  
            int mid = start+ (end- start)/2;  
            if (nums[mid] > nums[end]){  
                start = mid;  
            }  else {
                end = mid;
            }
         }
        return nums[start] < nums[end] ? nums[start] : nums[end];
    }
}

-------------------------------------------------------------------------------------------------------------------------
01/12/2018 update
Solution after refined template:

class Solution {
    public int findMin(int[] nums) {
        int target = nums[nums.length - 1], low = 0, high = nums.length;   
         while (low < high) {  
                int mid = low + (high - low)/2;  
                if (nums[mid] <= target) {  
                     high = mid;  
                } else {  
                     low = mid + 1;  
                }  
           }
           
        return nums[low];
    }
}

--------------------------------------------------------------------------------------------------------------------
01/11/2018 update
To avoid complexity, just compare nums[mid] with nums[length-1].
--------------------------------------------------------------------------------------------------------------------------
思路：
解法1：
自己的想法。先取的数组的第一个数first, 和最后一个数last。如果mid > first说明target在数组右边，否则在数组左边。实现的时候要注意没有rotate的特殊情况，需要加上if(nums[mid] < last && nums[mid] > first)来判断。

 public int findMin(int[] nums) {  
     // write your code here  
     int start = 0;  
     int end = nums.length-1;  
     int first = nums[0];  
     int last = nums[nums.length-1];  
     while( start+1 < end)  
     {  
       int mid = start+(end-start)/2;  
       if(nums[mid] < last && nums[mid] > first)  
       {  
         return first;  
       }  
       if(nums[mid] > first)  
       {  
         start = mid;  
       }  
       else if(nums[mid] < last)  
       {  
         end = mid;  
       }  
     }  
     return nums[start] < nums[end] ? nums[start] : nums[end];  
   }  

解法2：
九章的解法。就和last比，比last小在左边，比last大在右边。

  public int findMin(int[] nums) {  
     if (nums == null || nums.length == 0) {  
       return -1;  
     }  
     int start = 0, end = nums.length - 1;  
     int target = nums[nums.length - 1];  
     // find the first element <= target  
     while (start + 1 < end) {  
       int mid = start + (end - start) / 2;  
       if (nums[mid] <= target) {  
         end = mid;  
       } else {  
         start = mid;  
       }  
     }  
     if (nums[start] <= target) {  
       return nums[start];  
     } else {  
       return nums[end];  
     }  
   }