2021/01/21
题目描述
在上一题的基础上，允许重复元素的出现，只需要判断是否存在某个元素。
分析
先把这道题转化成 30 题，这样当我们求出 mid 之后，是可以判断 mid 所处的位置的。
实现
class Solution {
public boolean search(int[] nums, int target) {
return search(nums, target, 0, nums.length - 1);
}
public boolean search(int[] nums, int target, int i, int j) {
if (i > j) return false;
int l = nums[i], r = nums[j];
while (l == r && i < j) {
i += 1;
l = nums[i];
}
// 此时要么 l != r 了，要么 i == j 了
// 这个时候就是 33 题了
int idx = (i + j) / 2;
int n = nums[idx];
if (target == n) return true;
if (target == l) return true;
if (target == r) return true;
// 因为此时 n 的位置已经可以确定了，所以先讨论 n 的位置
if (n > r) { // 如果 n 在上
if (l < target && target < n) {
return search(nums, target, i + 1, idx - 1);
} else {
return search(nums, target, idx + 1, j - 1);
}
} else { // 如果 n 在下
if (n < target && target < r) { // t 在下
return search(nums, target, idx + 1, j - 1);
} else {
return search(nums, target, i + 1, idx - 1);
}
}
}
}