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

题目:

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

 

 

解答:

 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             else
19             {
20                 right = right - 1;                  /* 与不重复的只多这一行code*/
21             }
22         }
23 
24         return nums[left];    /* 循环结束,left == right,最小值输出nums[left]或nums[right]均可 */   
25 
26     }
27 };

 

上一篇:LeetCode 154. 寻找旋转排序数组中的最小值 II


下一篇:154. Find Minimum in Rotated Sorted Array II