首页 > 代码库 > [LeetCode] Search in Rotated Sorted Array II [36]

[LeetCode] Search in Rotated Sorted Array II [36]

题目

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.

原题链接(点我)

解题思路

这题和Search in Rotated Sorted Array问题类似,不过这个题允许元素重复,如果有元素重复,此时采取最保守的策略,一次缩小一个范围。

代码实现

class Solution {
public:
    bool search(int A[], int n, int target) {
        if(A==NULL || n<=0) return false;
        int begin = 0, end = n-1, mid = 0;
        while(begin<=end){
            mid = (begin+end)/2;
            if(A[mid] == target) return true;
            if(A[mid] < A[end]){
                //后半段有序
                if(A[end]>=target && A[mid]<target)
                    begin = mid+1;
                else
                    end =  mid - 1;
            }else if(A[mid] > A[end]){
                //前半段有序
                if(A[begin]<=target && A[mid] > target)
                    end = mid-1;
                else
                    begin = mid+1;
            }else
                // 最保守策略,缩小一个范围
                --end;
        }
        return false;
    }
};

如果你觉得本篇对你有收获,请帮顶。
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
你可以搜索公众号:swalge 或者扫描下方二维码关注我

(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/30487759 )