对于nums[left] == nums[mid] == nums[right]
情况,如nums=[3,1,2,3,3,3,3]
, target=2
nums[0] == nums[3] == nums[6] == 3,无法判断该搜索左侧区域还是右侧区域,一个简单的想法是同时缩小左右侧区域
nums=[3,1,2,3,3,3,3]
=> nums=[1,2,3,3,3]
class Solution {
public:
bool search(vector<int>& nums, int target) {
int size = nums.size();
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return true;
// 关键:对于重复元素nums[left] = nums[mid] = nums[right]难以判断target在哪个区间
// 那就缩小[left, right]区间,即left++; right--;
else if (nums[mid] == nums[left] && nums[mid] == nums[right]) {
left++;
right--;
} else if (target < nums[mid]) {
if (nums[left] > nums[mid] || (nums[left] < nums[mid] && target >= nums[left]))
right = mid - 1;
else left = mid + 1;
} else if (target > nums[mid]) {
if (nums[mid] > nums[right] || (nums[mid] < nums[right] && target <= nums[right]))
left = mid + 1;
else right = mid - 1;
}
}
return false;
}
};