陈中正的网络日志

LeetCode: Search in Rotated Sorted Array II

题目

https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/

分析

这道题是Search in Rotated Sorted Array的变形,因为有重复元素的存在,之前的方法就不不能直接用了,比如在{1, 3, 1, 1, 1}中寻找3, 结果就会出错。

出错的原因在于因为重复元素的存在,A[m]==A[l]时就不能确定在中点的哪一边是有序的,那就不能砍掉一半的查找范围了。

解决的办法是将左边界向右移动,直至A[m]!=A[l],这样一来在最坏情况下时间复杂度会变为O(n)。

源码

class Solution
{
public:
    bool search(int A[], int n, int target)
    {
        int l = 0;
        int r = n - 1;
        int m;

        while (l <= r)
        {
            m = (l + r) >> 1;
            if (A[m] == target)
                return true;
            else
            {
                if (A[m] == A[l])
                    l++;
                else if (A[m] > A[l])
                {
                    if (target >= A[l] && target < A[m])
                        r = m - 1;
                    else
                        l = m + 1;
                }
                else
                {
                    if (target > A[m] && target <= A[r])
                        l = m + 1;
                    else
                        r = m - 1;
                }
            }
        }
        return false;
    }
};

参考

http://blog.csdn.net/linhuanmars/article/details/20588511

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40156301

Categories:  OJ题解 

« APUE第三版源码编译问题解决[更新中。。] LeetCode: Search in Rotated Sorted Array »