81. Search in Rotated Sorted Array II

First, please read this problem and the solution:

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).