Search in Rotated Sorted Array I&&II——二分法

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)>>1;  
            if(A[mid]>target)  
            {  
                R=mid-1;  
            }  
            else if(A[mid]<target)  
            {  
                L=mid+1;  
            }  
            else    return mid;  
        }  
        return -1;  
    }  
   
   
    int search(vector<int>& nums, int target) {  
        int n=nums.size();
        vector<int> A(nums);
        if(n == 0)  return -1;  
        if(n == 1)  
        {  
            if(A[0] == target)  return 0;  
            else    return -1;  
        }  
        if(n == 2)  
        {  
            if(A[0] == target)  return 0;  
            else if(A[1] == target) return 1;  
            else    return -1;  
        }  
        int L=0,R=n-2;  
        while(L<R)//[0,n-2]找一个比A[n-1]大的数  
        {  
            int mid=(L+R>>1)+1;  
            if(A[mid]>A[n-1])   L=mid;  
            else  R=mid-1;  
        }  
        int split=L;  
        if(A[L]<A[n-1]) split=n-1;  
        //[0,split],[split+1,n-1]  
        int ans;  
        ans=search_2(A,0,split,target);  
        if(ans!=-1) return ans;  
        if(split+1<=n-1)  
        {  
            return search_2(A,split+1,n-1,target);  
        }  
        return -1;  
    }
};

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)/2;
        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+1;
                else
                    right=mid;
                return subSearch(nums,left,right,target);    
            }
                
        }
        else 
            return subSearch(nums,left,mid,target)|| subSearch(nums,mid+1,right,target);
    }
    bool search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        return subSearch(nums,left,right,target);
    }
};