lintcode-binarysearch-minimum-in-rotated-sorted-array

https://www.lintcode.com/problem/find-minimum-in-rotated-sorted-array/description

题目的意思：首先有一个排好序的数组，左边x个元素移动至最右端成为rotated 【注意这题没有重复的数字，如果有重复的数字，logN做不了 --- 不满足ooooxxxx存在明显分界线的情况】

【思路】找分界 --- oooxxx，依然是找第一个满足条件的位置
什么条件？--- 找左边和右边数的不同：e.g. 4 5 6 7| 0 1 2   
不同1：左边的所有数都>=2, 右边的所有数都<=2 --- version 2：以2为target，找数中第一个比他小的数（找第一个符合条件的问题） ---更好理解
不同2: 左边的数定义任意左右指针，都是左小于右，没有包含分界点；而对于整个数组，任意定义左右指针，若出现左大于右，则是包含分界点
所以分类讨论：1.比较左右指针，左小于右则没包含分界点，左大于右看第二个分类情况 2. 比较mid与右，mid<=右，不含分界，往右（因为找第一个）；mid>右，往左

//【Verision1】 --- 比较left和right指针处的值，成上升状态则有序，否则无序，找到第一个越过无序边界的位class Solution {
public:
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    int findMin(vector<int> &nums) {
        if(nums.empty())
            return -1;
            
        // write your code here
        int left = 0, right = nums.size() - 1;
        while (nums[left] > nums[right]) { //题目中时候不含重复元素 //这里左边比右边大 -- range(left,etight)中是乱序状态
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right])   //当mid位置的比右侧大时，说明在mid~right中存在乱序，寻找区间就需要向右移动
                left = mid+1;//【+1不能少】 例子：[2,1] 算出的mid = 0，right = 1，若left = mid 会一直循环
            else //小于右移，等于时 mid与right处数值相等，end = mid 在往左边找，因为要找的是第一个
                right = mid;//否则左移
        }
        
        //详细情况讨论
        // while(nums[left] > nums[right]){
        //     int mid = left + (right - left) / 2;
            
        //     if(nums[mid] > nums[right])
        //         left = mid + 1;
        //     if(nums[mid] < nums[right]) //mid 小于right, mid可能是分界点 e.g. 4 5 6 7| 0 1 2   mid=0，right=2
        //         right = mid;
                
        //     if(nums[mid] = nums[right])//mid 小于right, mid可能是分界点
        //         right = mid;
        // }

        return nums[left]; //返回left指针处//因为 while (nums[left] > nums[right]) ，循环停止时一定是left小于right或者重合的时候
    }
};


//【Version2】 --- 把末尾的值作为target, 从左往右找数中第一个小于target的值
public class Solution {
    /**
     * @param nums: 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;
        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) { 		//如果mid位置上的数字小于等于最右端的数字时，区间向左移动
                end = mid;
            } else {
                start = mid;			 
            }

            //详细情况分界：
            // if(nums[mid] == target)
            //     end = mid;
            // if(nums[mid] < target)
            //     end = mid;
            // if(nums[mid] > target)
            //     start = mid + 1; //这样写上方while可以写start < end

        }

        //第一个小于target的元素可能在start中也可能在end中
        return min(nums[start],nums[end]);  //最终返回start和end位置上较小的数字即可
        
    }
}