# C++ solution: avoid linear deleting repeating nums

• ``````        bool search(vector<int>& nums, int target) {
/* most posted solutions here use linear time deleting repeating numbers.
this will result in o(n) time while log time is possible. the solution below avoided linear deleting,
and shall prove time complexity somehow. */
vector<int> lstack, rstack;
int len=nums.size();
lstack.push_back(0);
rstack.push_back(len-1);

while (!lstack.empty()) {
int l=lstack.back(), r=rstack.back();
lstack.pop_back();
rstack.pop_back();

while (l<=r) {
int m=l+(r-l)/2;
if (nums[m]==target)
return true;

if (nums[m] < nums[r] || nums[m] < nums[l]) {
if (nums[m]<target && target<=nums[r])
l=m+1;
else
r=m-1;
} else if (nums[m] > nums[r] || nums[m] > nums[l]) {
if (nums[l]<=target && target<nums[m])
r=m-1;
else
l=m+1;
} else {
/* nums[l]=nums[m]=nums[r], we search for left half, and save right half for later */
lstack.push_back(m+1);
rstack.push_back(r);
r=m-1;
}
}

}

return false;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.