題目描述：與33題不同的是序列中可能有重復(fù)數(shù)字。找到返回true困乒，否則false寂屏。
分析：33題可以二分是因為每次總是至少有一半序列是有序的。有重復(fù)后則不能靠A[m] >= A[l]來判定[l,m]有序顶燕，如[ 1, 3, 1, 1, 1]凑保。則拆分為兩個條件：
- 若A[m] > A[l]，則[l,m]有序
- 若A[m] == A[l]涌攻，則不能判定[l,m]有序欧引，l++下移一步。
由于有后移操作故最壞情況可能一直后移恳谎，時間復(fù)雜度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;
}
};
