标签： 二分查找

目标

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且
• lower <= nums[i] + nums[j] <= upper

示例 1：

输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。

示例 2：

输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。

说明：

• 1 <= nums.length <= 10^5
• nums.length == n
• -10^9 <= nums[i] <= 10^9
• -10^9 <= lower <= upper <= 10^9

思路

计算数组中公平数对的个数，定义公平数对 (i, j) 满足 0 <= i < j < n && lower <= nums[i] + nums[j] <= upper。

对于下标 i，与之匹配的下标 j 需满足 j > i && lower - nums[i] <= nums[j] <= upper - nums[i]。公平数对下标不能相同，只要没有重复组合 i < j 或者 j < i 都可以，不关心相对位置，可以排序。

针对每一个下标 i 在 [i + 1, n - 1] 内二分查找上下界，计算其中的元素个数即可。

代码

/**
 * @date 2025-04-19 21:41
 */
public class CountFairPairs2563 {

    public long countFairPairs(int[] nums, int lower, int upper) {
        long res = 0L;
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int l = lowerBound(i + 1, n - 1, lower - nums[i], nums);
            int r = upperBound(i + 1, n - 1, upper - nums[i], nums);
            res += r - l + 1;
        }
        return res;
    }

    public int lowerBound(int left, int right, int target, int[] nums) {
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (target <= nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = left + (right - left) / 2;
        }
        return left;
    }

    public int upperBound(int left, int right, int target, int[] nums) {
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (target >= nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            mid = left + (right - left) / 2;
        }
        return right;
    }

}

性能

目标

给你一个二维整数数组 items ，其中 items[i] = [pricei, beautyi] 分别表示每一个物品的 价格 和 美丽值 。

同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 。

请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。

示例 1：

输入：items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
输出：[2,4,5,5,6,6]
解释：
- queries[0]=1 ，[1,2] 是唯一价格 <= 1 的物品。所以这个查询的答案为 2 。
- queries[1]=2 ，符合条件的物品有 [1,2] 和 [2,4] 。
  它们中的最大美丽值为 4 。
- queries[2]=3 和 queries[3]=4 ，符合条件的物品都为 [1,2] ，[3,2] ，[2,4] 和 [3,5] 。
  它们中的最大美丽值为 5 。
- queries[4]=5 和 queries[5]=6 ，所有物品都符合条件。
  所以，答案为所有物品中的最大美丽值，为 6 。

示例 2：

输入：items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
输出：[4]
解释：
每个物品的价格均为 1 ，所以我们选择最大美丽值 4 。
注意，多个物品可能有相同的价格和美丽值。

示例 3：

输入：items = [[10,1000]], queries = [5]
输出：[0]
解释：
没有物品的价格小于等于 5 ，所以没有物品可以选择。
因此，查询的结果为 0 。

说明：

• 1 <= items.length, queries.length <= 10^5
• items[i].length == 2
• 1 <= pricei, beautyi, queries[j] <= 10^9

思路

有一个二维数组 items，其元素 items[i] = [pricei, beautyi] 表示 item 的价格与美丽值。有一个查询数组，每一次查询的目标是找出价格小于等于 queries[i] 的物品中的最大美丽值。

为了求得答案，需要知道小于 queries[i] 都有哪些物品，然后从中找出最大美丽值。

先将 items 按照价格从小到大排序，二分查找 queries[i] 的上界下标 end。剩下的问题是找出 [0, end] 范围内的最大美丽值，这些值是固定的，可以预处理。

代码

/**
 * @date 2025-03-09 22:44
 */
public class MaximumBeauty2070 {

    public int[] maximumBeauty(int[][] items, int[] queries) {
        int n = items.length;
        Arrays.sort(items, (a, b) -> a[0] - b[0]);
        int[] maxBeauty = new int[n];
        maxBeauty[0] = items[0][1];
        for (int i = 1; i < n; i++) {
            maxBeauty[i] = Math.max(maxBeauty[i - 1], items[i][1]);
        }
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int upperbound = bs(queries[i], items);
            if (upperbound >= 0 && upperbound < n) {
                res[i] = maxBeauty[upperbound];
            }
        }
        return res;
    }

    public int bs(int target, int[][] items) {
        int n = items.length;
        int left = 0, right = n - 1;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (items[mid][0] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = left + (right - left) / 2;
        }
        return right;
    }

}

性能

目标

请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。

子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。

请你实现 RangeFreqQuery 类：

• RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
• int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。

一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。

示例 1：

输入：
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
输出：
[null, 1, 2]

解释：
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。

说明：

• 1 <= arr.length <= 10^5
• 1 <= arr[i], value <= 10^4
• 0 <= left <= right < arr.length
• 调用 query 不超过 10^5 次。

思路

设计一个数据结构，能够求出给定元素在子数组中的出现次数。

可以使用哈希表保存每个元素的下标列表（从小到大），查询时根据 value 获取下标列表，二分查找左边界的下界（第一个大于等于左边界的下标）和右边界的上界（最后一个小于等于右边界的下标）。注意二分查找的范围是 0 ~ list.size()，但是比较的则是原数组中的下标。构建时间复杂度为 O(n)，查询时间复杂度为 O(logn)。

代码

/**
 * @date 2025-02-18 15:57
 */
public  class RangeFreqQuery {

    public Map<Integer, List<Integer>> valueIndexMap = new HashMap<>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            valueIndexMap.putIfAbsent(arr[i], new ArrayList<>());
            valueIndexMap.get(arr[i]).add(i);
        }
    }

    public int query(int left, int right, int value) {
        List<Integer> list = valueIndexMap.get(value);
        if (list == null) {
            return 0;
        }
        return getUpperBound(right, list) - getLowerBound(left, list) + 1;
    }

    public int getUpperBound(int target, List<Integer> list) {
        int l = 0, r = list.size() - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (list.get(m) > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

    public int getLowerBound(int target, List<Integer> list) {
        int l = 0, r = list.size() - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (list.get(m) < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

}

性能

目标

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。

给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。

示例 1：

输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。

示例 2：

输入：position = [5,4,3,2,1,1000000000], m = 2
输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。

说明：

• n == position.length
• 2 <= n <= 10^5
• 1 <= position[i] <= 10^9
• 所有 position 中的整数 互不相同 。
• 2 <= m <= position.length

提示：

• If you can place balls such that the answer is x then you can do it for y where y < x.
• Similarly if you cannot place balls such that the answer is x then you can do it for y where y > x.
• Binary search on the answer and greedily see if it is possible.

思路

将 m 个球放到 n 个空篮子中，任意两个球之间的磁力为 |position[a] - position[b]|，返回最大的磁力最小值。

看到最大化最小值就想到二分，n 个盒子放 m 个球，每个盒子至多放 1 个。假定最小磁力为 y，即相邻球的磁力最少为 y。将 position 排序，累加相邻元素的差即磁力，如果大于 y 则放置一个球，看能否放得下。

代码

/**
 * @date 2025-02-14 9:35
 */
public class MaxDistance1552 {

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int n = position.length;
        int left = 0, right = position[n - 1] / (m - 1);
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(mid, position, m - 1)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            mid = left + (right - left) / 2;
        }
        return right;
    }

    public boolean check(int mid, int[] position, int m) {
        int start = position[0];
        for (int i = 1; i < position.length; i++) {
            if (position[i] >= start + mid) {
                if (--m == 0) {
                    return true;
                }
                start = position[i];
            }
        }
        return false;
    }

}

性能

目标

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

• 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
• 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例 1：

输入：nums = [9], maxOperations = 2
输出：3
解释：
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

示例 2：

输入：nums = [2,4,8,2], maxOperations = 4
输出：2
解释：
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。

示例 3：

输入：nums = [7,17], maxOperations = 2
输出：7

说明：

1 <= nums.length <= 10^5
1 <= maxOperations, nums[i] <= 10^9

思路

有 n 个袋子，nums[i] 表示第 i + 1 个袋子中球的数目。每次操作可以任选一个袋子，将其中的球分成非空的两部分并装入两个 新 袋子。求执行 maxOperations 次操作后袋中球的数量最大值的最小值是多少。

考虑暴力解法，要最小化最大值，我们应该首先操作球最多的袋子，划分方案有 max / 2 种。这里需要枚举所有划分方案，然后重新计算球最多的袋子重复这一处理流程。最坏的情况下所有元素值都相等，时间复杂度为 O((max/2)^maxOperations)。这种解法显然行不通。

既然正向思维行不通，那就考虑逆向思维。假定一个最大值 mid，看能否在 maxOperations 次操作内将所有袋子种的球都降到 mid 以下。

将数字 num 拆分成不大于 mid 的数字最少需要操作几次？这里可以使用贪心思想，将 num 拆分为 num - mid 和 mid，然后接着拆分 num - mid 直到它小于等于 mid。

关于次数的计算，如果 num % mid == 0，我们只需划分 num / mid - 1 次，因为剩余的部分为 mid。如果余数不为 0，则需要划分 num / mid 次。以上两种情况可以统一写成 (num - 1) / mid。

代码

/**
 * @date 2025-02-12 0:03
 */
public class MinimumSize1760 {

    public int minimumSize(int[] nums, int maxOperations) {
        int left = 1, right = 1000000000;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(nums, mid, maxOperations)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = left + (right - left) / 2;
        }
        return left;
    }

    public boolean check(int[] nums, int mid, int maxOperations) {
        for (int num : nums) {
            maxOperations -= (num - 1) / mid;
            if (maxOperations < 0) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

说明：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

进阶：

此题与 33.搜索旋转排序数组 相似，但本题中的 nums 可能包含 重复 元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

思路

将 有序数组 划分为两个子数组，交换子数组的顺序得到旋转数组 nums，判断旋转数组中是否存在 target。

根据题意可知，原来的有序数组被划分成两部分，第一部分的所有元素均大于 等于 第二部分的所有元素。

此题与 33.搜索旋转排序数组 相似，但本题中的 nums 可能包含 重复 元素。如果当前元素恰好与切点的元素值相同，那么我们无法判断该搜索哪一部分。

例如，如果当前元素值大于 target，但是恰好与第一个元素相同：

• 如果当前元素就是位于第一部分，那么我们应该将 left 左移，以便到达第二部分搜索。
• 如果当前元素已经位于第二部分，那么我们应该将 right 右移，以便找到更小的target。

最简单的处理方法是缩小右边界，因为这种情况只会出现在切点刚好在连续相同元素中间，这时最左侧的元素一定与最右侧的元素相同，我们可以提前将 right 移到第一个与 left 不同的位置。这样当前元素属于哪一部分就确定了，不会影响判断。

代码

/**
 * @date 2025-02-01 14:33
 */
public class Search81 {

    public boolean search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (right > 0 && nums[left] == nums[right]) {
            right--;
        }
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(nums[mid], nums[0], target)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            mid = left + (right - left) / 2;
        }
        if (left >= 0 && left < n) {
            return nums[left] == target;
        }
        return false;
    }

    public boolean check(int midValue, int firstValue, int target) {
        if (target < firstValue) {
            if (midValue >= firstValue) {
                return true;
            } else {
                return midValue < target;
            }
        } else {
            if (midValue >= firstValue) {
                return midValue < target;
            } else {
                return false;
            }
        }
    }

}

性能

目标

给你两个 正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的 真因数。

如果一个数字恰好仅有两个 真因数，则称该数字为 特殊数字。例如：

• 数字 4 是 特殊数字，因为它的真因数为 1 和 2。
• 数字 6 不是 特殊数字，因为它的真因数为 1、2 和 3。

返回区间 [l, r] 内 不是 特殊数字 的数字数量。

示例 1：

输入： l = 5, r = 7
输出： 3
解释：
区间 [5, 7] 内不存在特殊数字。

示例 2：

输入： l = 4, r = 16
输出： 11
解释：
区间 [4, 16] 内的特殊数字为 4 和 9。

说明：

• 1 <= l <= r <= 10^9

提示：

• A special number must be a square of a prime number.
• We need to find all primes in the range [sqrt(l), sqrt(r)].
• Use sieve to find primes till sqrt(10^9).

思路

返回给定区间 [l, r] 内不是特殊数字的数字个数，所谓特殊数字指除了它本身恰好有两个正因数的数字。

一看到数据范围是 10^9 就不可能使用使用暴力解法去判断每一个数字是不是 l 或 r 的因数，要么使用二分要么预处理。特殊数字是确定的，它除了自身以外只有两个因数，1 一定是一个，即除了 1 和它本身只有一个因数。看了提示说特殊数字是质数的平方，我们需要找到所有在 [√l, √r] 范围内的质数，可以预处理 √10^9 内的质数。二分查找 [l, r] 范围内质数的个数，然后减掉即可。

埃氏筛的基本思想是创建一个 boolean[] 标记查询范围内的数是否为质数，初始时均标记为 true。从 2 开始遍历（0和 1 后面直接过滤掉了)，直到 i < √end 即 i * i < end。在循环内部，如果当前值是质数，则将 i * i，i * (i + 1)，i * (i + 2)，…… 标记为非质数。比如在 2 的循环内，所有大于 2 的偶数都被标为非质数，以此类推，像筛子一样将质数筛选出来。

// todo 最后也可以使用前缀和计算个数

代码

/**
 * @date 2024-11-22 9:07
 */
public class NonSpecialCount3233 {

    public static int[] primes;

    static {
        List<Integer> primeList = new ArrayList<>();
        int end = (int) Math.ceil(Math.sqrt(1000000001));
        boolean[] isPrime = new boolean[end + 1];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i <= end; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= end; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        // 前面没有将 isPrime[0] isPrime[1] 置为false，这里从2开始
        for (int i = 2; i <= end; i++) {
            if (isPrime[i]) {
                primeList.add(i);
            }
        }
        int cnt = primeList.size();
        primes = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            primes[i] = primeList.get(i);
        }
    }

    public int nonSpecialCount_v1(int l, int r) {
        int ceilLeft = (int) Math.ceil(Math.sqrt(l));
        int right = (int) Math.sqrt(r);
        if (ceilLeft > right) {
            return r - l + 1;
        }
        int a = Arrays.binarySearch(primes, ceilLeft);
        if (a < 0) {
            // 获取插入点，说明原来该位置的值大于ceilLeft
            a = -a - 1;
        }
        int b = Arrays.binarySearch(primes, right);
        if (b < 0) {
            // 这里多减了1，因为插入点是第一个大于right的位置，减1则小于 right
            b = -b - 2;
        }
//        return r - l + 1 - (b - a + 1);
        return r - l - b + a;
    }

}

性能