YSMull
<-- algorithm



原题链接

题目描述

上一题的基础上,允许重复元素的出现,只需要判断是否存在某个元素。

分析

先把这道题转化成 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);
            }
        }
    }
}