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

 1 class Solution {
 2 public:
 3     int findMin(vector<int>& nums) 
 4     {
 5         int left = 0;
 6         int right = nums.size() - 1;                /* 左闭右闭区间，如果用右开区间则不方便判断右值 */ 
 7         while (left < right)                        /* 循环不变式，如果left == right，则循环结束 */
 8         {                      
 9             int mid = left + (right - left) / 2;    /* 地板除，mid更靠近left */
10             if (nums[mid] > nums[right])            /* 中值 > 右值，最小值在右半边，收缩左边界 */ 
11             {          
12                 left = mid + 1;                     /* 因为中值 > 右值，中值肯定不是最小值，左边界可以跨过mid */ 
13             } 
14             else if (nums[mid] < nums[right])       /* 明确中值 < 右值，最小值在左半边，收缩右边界 */
15             {    
16                 right = mid;                        /* 因为中值 < 右值，中值也可能是最小值，右边界只能取到mid处 */ 
17             }
18         }
19 
20         return nums[left];    /* 循环结束，left == right，最小值输出nums[left]或nums[right]均可 */   
21     }
22 };