#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) );    }*/