Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 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.
解题思路：
求旋转数组中是否存在某一个整数，若存在返回该值在数组中的下标，，否则返回-1.该数组中无重复数字。
方法：
参考Find Minimum in Rotated Sorted Array I
我们找到旋转数组中的最小的元素，也就相当于将旋转数组，分成两个递增数组的分界点知道了。我们在这两个有序数组中利用二分法找是否存在target即可，代码如下：
class Solution {public:int findMin(vector<int>& nums) {if(nums.size()==1) return 0;if(nums.size()==2){return nums[0]>nums[1]?1:0;}for(int i=0;i<nums.size()-1;i++){if(nums[i+1]<nums[i])return i+1;}return nums[0];}int search(vector<int>& nums, int target) {if(nums.size()==0) return -1;int dex=findMin(nums);if(dex==0){int low=0,high=nums.size()-1;while(low<=high){int mid=(low+high)/2;if(nums[mid]>target)high=mid-1;else if(nums[mid]<target)low=mid+1;elsereturn mid;}}else if(dex==nums.size()-1){if(nums[dex]==target)return dex;int low=0,high=nums.size()-2;while(low<=high){int mid=(low+high)/2;if(nums[mid]>target)high=mid-1;else if(nums[mid]<target)low=mid+1;elsereturn mid;}}else{int low=0,high=dex-1;while(low<=high){int mid=(low+high)/2;if(nums[mid]>target)high=mid-1;else if(nums[mid]<target)low=mid+1;elsereturn mid;}low=dex,high=nums.size()-1;while(low<=high){int mid=(low+high)/2;if(nums[mid]>target)high=mid-1;else if(nums[mid]<target)low=mid+1;elsereturn mid;}}return -1;}};
Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":What ifduplicatesare allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
解题思路：方法：
参考
Find Minimum in Rotated Sorted Array II
同Search in Rotated Sorted Array I，相同思路，代码如下：
class Solution {public: int findMin(vector<int>& nums) {if(nums.size()==1) return 0;if(nums.size()==2) return nums[0]<nums[1]?0:1;for(int i=0;i<nums.size()-1;i++){if(nums[i+1]<nums[i])return i+1;}return nums.size()-1;}bool search(vector<int>& nums, int target) {if(nums.size()==0) return false;int dex=findMin(nums);if(dex==0){int low=0,high=nums.size()-1;while(low<=high){int mid=(low+high)/2;if(nums[mid]>target)high=mid-1;else if(nums[mid]<target)low=mid+1;elsereturn true;}}else if(dex==nums.size()-1){if(nums[dex]==target)return true;int low=0,high=nums.size()-2;while(low<=high){int mid=(low+high)/2;if(nums[mid]>target)high=mid-1;else if(nums[mid]<target)low=mid+1;elsereturn true;}}else{int low=0,high=dex-1;while(low<=high){int mid=(low+high)/2;if(nums[mid]>target)high=mid-1;else if(nums[mid]<target)low=mid+1;elsereturn true;}low=dex,high=nums.size()-1;while(low<=high){int mid=(low+high)/2;if(nums[mid]>target)high=mid-1;else if(nums[mid]<target)low=mid+1;elsereturn true;}}return false;}};
别人失去了信心，他却下决心实现自己的目标。
