题目描述：与33题不同的是序列中可能有重复数字。找到返回true，否则false。
分析：33题可以二分是因为每次总是至少有一半序列是有序的。有重复后则不能靠A[m] >= A[l]来判定[l,m]有序，如[ 1, 3, 1, 1, 1]。则拆分为两个条件：
- 若A[m] > A[l]，则[l,m]有序
- 若A[m] == A[l]，则不能判定[l,m]有序，l++下移一步。
由于有后移操作故最坏情况可能一直后移，时间复杂度O(n)，空间O(1)。
代码：
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l =0, r = nums.size();
while(l != r)
{
int mid = (l + r) / 2;
if (nums[mid] == target)
return true;
if (nums[l] < nums[mid]) //l ~ mid无断点 {
if (nums[l] <= target && target < nums[mid])
r = mid;
else
l = mid + 1;
}
else if (nums[l] > nums[mid]) //l ~ mid有断点，即mid ~ r无断点
{
if (nums[mid] < target && target <= nums[r - 1])
l = mid + 1;
else
r = mid;
}
else //此时nums[l] == nums[mid] != target，故直接后移
l ++;
}
return false;
}
};
