leecode 解题总结：153. Find Minimum in Rotated Sorted Array

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题:Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).Find the minimum element.You may assume no duplicate exists in the array.分析:找到旋转数组中最小的元素。之前是做了找到旋转数组中某个元素是否存在。这里假设没有重复。最小的元素：前面是最大的元素。最大的元素在升序部分中。如果中间 > 左边，说明左边是升序，最小的元素就是在右半部分(中间不可能)。4 5 6 7 0 1 2如果中间 < 左边，右边是升序，最小的元素应该在左半部分(中间元素也有可能)，比如6 7 8 0 1 2 3 4 5                                                           4 5 6 0 1 2 3直到low = high，输出结果这个应该是二分查找。输入:7(数组元素个数)4 5 6 7 0 1 296 7 8 0 1 2 3 4 574 5 6 0 1 2 331 2 321 211输出:000111关键:1另一种解法：https://leetcode.com/PRoblems/find-minimum-in-rotated-sorted-array/?tab=Solutions左边 < 右边，升序，无旋转，直接返回最左边否则，左边 <= 中间，左边到中间无旋转，最小值在右侧(不包含左边)否则，右边升序，但是在左边，包含中间值2 报错:1 2 3，如果没有逆转，发现有问题。按照之前的逻辑左边 <中间，答案在右半部分如果左边<中间<右边，说明是升序，直接返回最左边的；3 非升序：左边 < 中间，左边升序，答案在右边，且包含中间值左边 > 中间，右边升序，答案在左边，且包含中间值左边 = 中间，说明出现low = mid，跳出，则结果在A[low]和A[high]的最小值中*/class Solution {public:    int findMin(vector<int>& nums) {       if(nums.empty())	   {		   return 0;	   }	   int low = 0;	   int high = nums.size() - 1;//长度为数组值减1	   int mid;	   while(low < high)	   {		   mid = low + (high - low) / 2;		   //升序，返回最左边		   if(nums.at(low) < nums.at(high))		   {			   return nums.at(low);		   }		   //左边小于中间，左边有序，答案在右边，不包含中间值(中间值很大), 1 2 3 0 -1 		   // = 说明low = mid。此时需要提高low		   if(nums.at(low) <= nums.at(mid))		   {			   low = mid + 1;		   }		   //左边 > 中间 < 右边，答案在左边，包含中间值		   else		   {			   high = mid;		   }	   }	   return nums.at(low);	}};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 int result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 result = solution.findMin(nums);		 cout << result << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}/*    int findMin2(vector<int>& nums) {       if(nums.empty())	   {		   return 0;	   }	   int low = 0;	   int high = nums.size() - 1;//长度为数组值减1	   int mid;	   while(low < high)	   {		   mid = low + (high - low) / 2;		   //升序，直接返回最左侧元素		   if(nums.at(low) < nums.at(mid) && nums.at(mid) < nums.at(high))		   {			   return nums.at(low);		   }		   //非升序		   else		   {			   //如果出现low = mid，应该就是			   //左边 < 中间，左边升序，答案在右区间，且包含中间值,参见如果0 1的时候，0是最小值			   if(nums.at(low) < nums.at(mid))			   {				   low = mid;			   }			   //左边 > 中间，右边升序，答案在左区间，且包含中间值			   else if(nums.at(low) > nums.at(mid))			   {				   high = mid;			   }			   //如果两者相等，应该就是low = mid,high比low大1，结果值在low和high其中的一个			   else			   {				   break;			   }		   }	   }	   //如果low = high,返回	   return min( nums.at(low) , nums.at(high) );    }*/