【leetcode】153. 寻找旋转排序数组中的最小值

题目链接：传送门

题目描述

现有一个有序数组，假设从某个数开始将它后面的数按顺序放到了数组前面。(即 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2])。

请找出数组中的最小元素。

数组中不包含重复元素。

样例1

　　输入：[3,4,5,1,2]

　　输出：1

样例2

　　输入：[4,5,6,7,0,1,2]

　　输出：0

题解来源：传送门

算法(二分) O(logn)
处理这种问题有个常用技巧：如果不想处理边界情况，比如当数组只有两三个数的时候，代码会出问题。我们可以在数组长度太短(这道题中我们判断数组长度小于5)时，直接暴力循环做；数组有一定长度时再用二分做。
这样做并不会影响算法的时间复杂度，但会缩短写代码的时间。

为了便于理解，我们将数组中的数画在二维坐标系中，横坐标表示数组下标，纵坐标表示数值，如下所示：

我们会发现数组中最小值前面的数 nums[i]nums[i] 都满足：nums[i]≥nums[0]，其中nums[n−1] 是数组最后一个元素；而数组中最小值后面的数（包括最小值）都不满足这个条件。
所以我们可以二分出最小值的位置。

另外，不要忘记处理数组完全单调的特殊情况。

时间复杂度分析：二分查找，所以时间复杂度是 O(logn)。

 1 class Solution {
 2 public:
 3     int findMin(vector<int>& nums) {
 4         if ( nums[0] < nums.back() ) return nums[0] ;
 5         int L = 0 , R = nums.size() -1 , Mid , ans = 0 ; 
 6         while ( L < R ){
 7             Mid = L+R >> 1 ; 
 8             if( nums[0] <= nums[Mid] ){
 9                 ans = Mid ;
10                 L = Mid + 1 ;
11             }else {
12                 R = Mid  ;
13             }
14         }
15         return nums[L] ; 
16     }
17 };