#include <iostream>#include <stdio.h>#include <vector>using namespace std;/*問(wèn)題: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).You are given a target value to search. If found in the array return its index, otherwise return -1.You may assume no duplicate exists in the array.分析:這是程序員面試金典的一道題目。是在旋轉(zhuǎn)數(shù)組中查找一個(gè)元素。設(shè)數(shù)組為A,長(zhǎng)度為len,設(shè)查找元素為target，設(shè)旋轉(zhuǎn)的樞軸為pivot，初始low=0,high=len-1mid = low + (high-low)/2; 如果A[low] < target,那么元素只可能在旋轉(zhuǎn)數(shù)組的左側(cè)部分(因?yàn)锳[low]~A[pivot]是升序的，A[pivot+1]~A[high]是升序的，且A[0]>A[len-1])  令high = mid如果A[low] > target，元素在旋轉(zhuǎn)數(shù)組的右側(cè)部分  令low = midA[low] = target，找到元素，返回lowlow > high，返回-1，表示找不到輸入:7 64 5 6 7 0 1 27 24 5 6 7 0 1 27 34 5 6 7 0 1 26 32 3 2 2 2 26 32 2 2 2 3 26 32 2 2 2 2 4輸出:26-114-1關(guān)鍵:1 需要用中間元素和兩邊元素比較來(lái)確定哪一邊是升序，并根據(jù)升序兩側(cè)大小和給定值比較，確定最終在A[low] < A[mid]說(shuō)明左邊是升序，例如4 5 6 7 0 1 2，如果有A[low] <= target <= A[high]，則在左半部分尋找A[low] > A[mid]說(shuō)明右邊是升序，例如5 6 7 0 1 2 42左邊=中間 != 右邊，在右半部分查找 左邊=中間 = 右邊，先左半部分查找，如果左半部分查找不到，查找右半部分*/class Solution {public:    int searchRotation(vector<int>& nums, int target ,int low ,int high) {        if(nums.empty() ||low < 0 || high >= nums.size() || low > high)		{			return -1;		}		int mid;		if(low < high)		{			mid = low + (high - low)/2;			//找到元素			if(nums.at(mid) == target)			{				return mid;			}			//左半部分升序			if(nums.at(low) < nums.at(mid))			{				//在左半部分升序中				if( nums.at(low) <= target && target <= nums.at(mid))				{					//high = mid;					return searchRotation(nums, target , low , mid);				}				//在右半部分中尋找				else				{					//low = mid + 1;					return searchRotation(nums , target , mid + 1 , high);				}			}			//右半部分升序			else if(nums.at(low) > nums.at(mid))			{				//在右半部分升序中				if(nums.at(mid) <= target && target <= nums.at(high))				{					//low = mid;					return searchRotation(nums , target , mid , high);				}				else				{					//high = mid - 1;					return searchRotation(nums , target , low , mid - 1);				}			}			//左邊等于中間，可能low=high=mid時(shí)進(jìn)入			else			{				//如果左邊!=右邊，查找右半部分				if(nums.at(low) != nums.at(high))				{					//low = mid + 1;					return searchRotation(nums , target , mid + 1, high);				}				//左邊=中間=右邊，先查左半部分，再查右半部分				else				{					int result = searchRotation(nums , target , low , mid);					if(-1 != result)					{						return result;					}					else					{						return searchRotation(nums , target , mid + 1 , high);					}				}			}		}		//low == high		else		{			if(nums.at(low) == target)			{				return low;			}			else			{				return -1;			}		}    }    int search(vector<int>& nums, int target) {        if(nums.empty())		{			return -1;		}		int len = nums.size();		int low = 0;		int high = len - 1;		int result = searchRotation(nums , target , low , high);		return result;    }};void PRocess(){	int value;	int num;	vector<int> datas;	int searchValue;	while(cin >> num >> searchValue)	{		datas.clear();		for(int i = 0 ; i < num ; i++)		{			cin >> value;			datas.push_back(value);		}		Solution solution;		int result = solution.search(datas , searchValue);		cout << result << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}