题目:
解答:
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 };