# 81. Search in Rotated Sorted Array II

First, I wrote down the following code without any doubt:

`class Solution {public:    bool search(vector<int>& nums, int target) {        if (nums.empty()) {            return false;        }                const auto pivot = nums.front();        const auto isInFirstHalf = target >= pivot;                auto first = nums.begin();        auto last = nums.end();                auto lb = std::lower_bound(first, last, target, [=](const int a, const int b){            return adjustValue(a, pivot, isInFirstHalf) < b;        });                return lb != nums.end() && *lb == target;    }        int adjustValue(const int origin, const int pivot, const bool isInFirstHalf) {        return isInFirstHalf?             (origin < pivot? INT_MAX: origin):            (origin < pivot? origin: INT_MIN);    }};`

But I failed in this test case:

`[1,3,1,1]3`

Do read the problem carefully, it mention specifically about existence of duplicates!

It seems that only duplicates appear in front or back will produce the above error, just a minor fix is enough.

`class Solution {public:    bool search(vector<int>& nums, int target) {        if (nums.empty()) {            return false;        }                const auto pivot = nums.front();        const auto isInFirstHalf = target >= pivot;                auto first = nums.begin();        auto last = stripTrailingDuplicates(nums.begin(), nums.end());                auto lb = std::lower_bound(first, last, target, [=](const int a, const int b){            return adjustValue(a, pivot, isInFirstHalf) < b;        });                return lb != nums.end() && *lb == target;    }        template <class Iter>    Iter stripTrailingDuplicates(Iter first, Iter last) {        const auto duplicate = *first;                while (first != last) {            --last;                        if (duplicate != *last) {                return last + 1;            }        }                return first;    }        int adjustValue(const int origin, const int pivot, const bool isInFirstHalf) {        return isInFirstHalf?             (origin < pivot? INT_MAX: origin):            (origin < pivot? origin: INT_MIN);    }};`

However the worse case is still O(n).