Search in Rotated Sorted Array I
Suppose a sorted array 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.
做完了Find Minimum in Rotated Sorted Array之后，对这题又发现了一种非常简单的做法。
Find Minimum in Rotated Sorted Array的思路如下：
当nums[left]<nums[right],说明数组没有旋转，是按升序排列的。可直接返回nums[left];
当nums[left]<nums[mid],说明left至mid这段是按升序排列的，可令left=mid+1;
当nums[left]>nums[mid],说明mid至right这段是按升序排列的，可令right=mid;
那么这题的解法也就出来了，把数组分成两部分，那肯定是有一部分是有序的，另一部分是无序的，不管有序还是无序，都对其继续进行二分搜索，最终肯定都能得到有序的数组，不过这样做感觉就不是二分搜索了，因为每次并没有去掉一半。
也是通过二分搜索来解决，先通过一个二分搜索找到旋转的点，再分别对前后两个有序数组使用二分搜索，思路很简单，代码也没自己写了。
转：http://blog.csdn.net/zhangwei1120112119/article/details/16829309
class Solution {
public:
int search_2(vector<int>& A, int L, int R, int target)
{
while(L<=R)
{
int mid=(L+R)>>;
if(A[mid]>target)
{
R=mid-;
}
else if(A[mid]<target)
{
L=mid+;
}
else return mid;
}
return -;
}
int search(vector<int>& nums, int target) {
int n=nums.size();
vector<int> A(nums);
if(n == ) return -;
if(n == )
{
if(A[] == target) return ;
else return -;
}
if(n == )
{
if(A[] == target) return ;
else if(A[] == target) return ;
else return -;
}
int L=,R=n-;
while(L<R)//[0,n-2]找一个比A[n-1]大的数
{
int mid=(L+R>>)+;
if(A[mid]>A[n-]) L=mid;
else R=mid-;
}
int split=L;
if(A[L]<A[n-]) split=n-;
//[0,split],[split+1,n-1]
int ans;
ans=search_2(A,,split,target);
if(ans!=-) return ans;
if(split+<=n-)
{
return search_2(A,split+,n-,target);
}
return -;
}
};Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
非常简单：
class Solution {
public:
bool subSearch(vector<int>& nums,int left,int right,int target)
{
if(left>right)
return false;
if(nums[left]==target)
return true;
while(nums[left]==nums[right]&&left<right)
left++;
if(left==right)
{
if(nums[left]==target)
return true;
else
return false;
}
int mid=(left+right)/;
if(nums[left]<nums[right])
{
if(nums[left]>target||nums[right]<target)
return false;
else
{
if(target==nums[mid])
return true;
if(target>nums[mid])
left=mid+;
else
right=mid;
return subSearch(nums,left,right,target);
}
}
else
return subSearch(nums,left,mid,target)|| subSearch(nums,mid+,right,target);
}
bool search(vector<int>& nums, int target) {
int left=;
int right=nums.size()-;
return subSearch(nums,left,right,target);
}
};