由一道题目所引发的对于二分查找的思考

一、题目描述

给你一个下标从 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

二、思路分析

显然这道题由于 nums 数组的长度不能直接用两个 for 循环来解决，观察题目要求，需要找到两个和在规定范围内的数，而这两个数的位置是没有要求的，所以我们可以先对数组进行排序，然后使用二分查找。

需要注意的是，这里的二分查找找的是第一个大于等于 lower - nums[i] 和第一个大于 upper - nums[i] 的位置。这里我们分别记作 begin 和 end，然后在这个范围内的数都可以和 nums[i] 构成一对公平数。

三、核心代码

// 始终返回第一个大于等于 index 的位置，注意和标准的二分查找区分
public int findIndex(int[] nums, int left, int right, int index) {
    int ans = right + 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] >= index) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

可以看到这个二分查找和标准的二分查找是有区别的，标准的二分查找目标是返回查找对象，而这里的目标是返回第一个大于等于目标对象的位置。

四、完整代码

class Solution {

    public long countFairPairs(int[] nums, int lower, int upper) {
        long count = 0;
        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n - 1; i++) {
            int begin = findIndex(nums, i + 1, n - 1, lower - nums[i]);
            // 注意这里
            int end = findIndex(nums, i + 1, n - 1, upper - nums[i] + 1);
            count += end - begin;
        }

        return count;
    }

    // 始终返回第一个大于等于 index 的位置
    public int findIndex(int[] nums, int left, int right, int index) {
        int ans = right + 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= index) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

}

五、思考与反思

这道题用到的是一种二分查找的变种，通常称为：二分查找第一个大于等于目标值的位置。这种二分边界问题的特点就是不在判断中返回结果，同理如果我要查找最后一个小于等于 target 的话那只需要改动 if 里面的判断条件然后修改 ans 的赋值位置即可。

下面列举一下这类方法的应用场景：

1. 范围统计问题

题目特点：给定一个有序数组和两个值 lower 和 upper，统计有多少个数在这个区间 [lower, upper] 中。

2. 前缀/差值对数统计

题目特点：在枚举某个值后，要通过二分找到另一个值的上下界区间，从而统计对数。

3. 查找边界/最近值（右边界/左边界）

  • 找最早 >= target 的位置 → 常用于滑动窗口左端点推进
  • 找最后 <= target 的位置 → 常用于滑动窗口右端点收缩