leecode 解题总结：33. Search in Rotated Sorted Array

#include <iostream>#include <stdio.h>#include <vector>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).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.分析:这是程序员面试金典的一道题目。是在旋转数组中查找一个元素。设数组为A,长度为len,设查找元素为target，设旋转的枢轴为pivot，初始low=0,high=len-1mid = low + (high-low)/2; 如果A[low] < target,那么元素只可能在旋转数组的左侧部分(因为A[low]~A[pivot]是升序的，A[pivot+1]~A[high]是升序的，且A[0]>A[len-1])  令high = mid如果A[low] > target，元素在旋转数组的右侧部分  令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关键:1 需要用中间元素和两边元素比较来确定哪一边是升序，并根据升序两侧大小和给定值比较，确定最终在A[low] < A[mid]说明左边是升序，例如4 5 6 7 0 1 2，如果有A[low] <= target <= A[high]，则在左半部分寻找A[low] > A[mid]说明右边是升序，例如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时进入			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;}