题解 | 【模板】整数域二分

import java.io.*;
import java.util.*;

public class Main {
    
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入，PrintWriter输出结果
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取第一行输入，分割成字符串数组
        String[] strA = br.readLine().trim().split("\\s+");

        // 解析数组长度n和查询次数q
        int n = Integer.parseInt(strA[0]);
        int q = Integer.parseInt(strA[1]);
        // 创建数组a并读取输入数据
        int[] a = new int[n];
        String[] strB = br.readLine().trim().split("\\s+");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(strB[i]);
        }

        // 对数组进行排序，为后续查询做准备
        Arrays.sort(a);
        // 处理q次查询
        while (q-- > 0) {
            // 读取每次查询的左右边界
            String[] strC = br.readLine().trim().split("\\s+");

            int l = Integer.parseInt(strC[0]);
            int r = Integer.parseInt(strC[1]);

            // 使用二分查找计算下界和上界
            int left = lowerBound(a, l);
            int right = upperBound(a, r);

            // 输出结果：范围内的元素个数
            out.println(right - left);

        }

        // 关闭IO资源
        out.flush();
        out.close();
        br.close();
    }

    /**
     * 二分查找下界函数
     *
     * @param a      已排序的数组
     * @param target 目标值
     * @return 第一个大于等于target的元素的索引
     */
    private static int lowerBound(int[] a, int target) {
        // 初始化查找范围的 low 和 high 指针
        // low 从数组的起始位置 0 开始
        // high 从数组长度开始（不包括该位置）
        int low = 0, high = a.length;

        // 当 low 小于 high 时，继续查找
        // 这是循环查找的条件，确保查找范围有效
        while (low < high) {
            // 计算中间位置 mid
            // 使用位运算 (high-low)>>1 代替除法 2，提高效率
            // 防止整数溢出，同时确保 mid 总是在 low 和 high 之间
            int mid = low + ((high - low) >> 1);

            // 如果中间位置的元素大于等于目标值
            // 说明目标值可能在左半部分，或者 mid 就是我们要找的位置
            // 因此将 high 设置为 mid，继续在左半部分查找
            if (a[mid] >= target) {
                high = mid;
            } else {
                // 如果中间位置的元素小于目标值
                // 说明目标值一定在右半部分
                // 因此将 low 设置为 mid+1，继续在右半部分查找
                low = mid + 1;
            }

        }
        // 当循环结束时，low 指向第一个大于等于 target 的元素的位置
        // 如果所有元素都小于 target，则返回数组长度
        return low;
    }

    /**
     * 二分查找上界函数
     *
     * @param a      已排序的数组
     * @param target 目标值
     * @return 第一个大于target的元素的索引
     */
    private static int upperBound(int[] a, int target) {
        // 初始化查找范围的左右边界，左边界为0，右边界为数组长度
        int low = 0, high = a.length;

        // 当左边界小于右边界时，继续查找
        while (low < high) {
            // 计算中间位置，使用位运算防止溢出
            int mid = low + ((high - low) >> 1);

            // 如果中间位置的值大于目标值，则上界在左半部分
            if (a[mid] > target) {
                high = mid;
            } else {
                // 否则上界在右半部分，且不包括中间位置
                low = mid + 1;
            }

        }
        // 返回第一个大于target的元素的索引
        return low;
    }
}