优化双数组循环：利用排序与二分查找提升性能

import java.util.ArrayList;
import java.util.List;

public class ArrayComparison {

    /**
     * 传统嵌套循环方法，统计数组a中大于等于b中每个元素的数量。
     * 性能较低，时间复杂度为 O(m*n)。
     *
     * @param a 整数数组a
     * @param b 整数数组b
     * @return 存储统计结果的列表
     */
    public static List<Integer> giantArmyInefficient(int a[], int b[]) {
        List<Integer> list = new ArrayList<>();
        // 针对特定边界条件（a只有一个0元素），可以提前返回，但这不是核心优化点
        if (a.length == 1 && a[0] == 0) {
            list.add(0);
            return list;
        }

        int count;
        for (int i = 0; i < b.length; i++) { // 外层循环遍历b
            count = 0; // 每次对b[i]的统计都需要重置计数器
            for (int j = 0; j < a.length; j++) { // 内层循环遍历a
                if (a[j] >= b[i]) {
                    count++;
                }
            }
            list.add(count);
        }
        return list;
    }

    public static void main(String[] args) {
        int[] arrA = {1, 2, 3, 4, 5};
        int[] arrB = {6, 5, 4, 3, 2};
        System.out.println("Inefficient result: " + giantArmyInefficient(arrA, arrB));
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArrayComparisonOptimized {

    /**
     * 优化后的方法，利用排序和二分查找统计数组a中大于等于b中每个元素的数量。
     * 时间复杂度为 O(n log n + m log n)。
     *
     * @param a 整数数组a
     * @param b 整数数组b
     * @return 存储统计结果的列表
     */
    public static List<Integer> giantArmyOptimized(int a[], int b[]) {
        int aLength = a.length;
        List<Integer> result = new ArrayList<>();

        // 步骤1: 对数组a进行排序
        Arrays.sort(a); // 时间复杂度 O(n log n)

        // 步骤2: 遍历数组b，并对每个元素在a中进行二分查找
        for (int target : b) { // 循环m次
            // 步骤3: 在已排序的a中查找target的插入点
            int index = Arrays.binarySearch(a, target); // 每次查找 O(log n)

            // 如果target不存在，index为负数，表示插入点
            if (index < 0) {
                index = -index - 1; // 转换为实际的插入点，即小于target的元素数量
            } else {
                // 如果target存在，需要找到第一个大于等于target的元素的索引。
                // Arrays.binarySearch可能返回任意一个匹配项的索引。
                // 为了正确统计，我们需要找到所有等于target的元素的起始位置。
                // 简单的做法是，如果找到，我们继续向左查找，直到找到第一个等于target的元素或越界。
                // 但对于“大于等于”的统计，直接使用返回的index是可行的，因为我们关心的是其右侧元素的数量。
                // 如果存在多个相同元素，binarySearch可能返回其中任意一个的索引。
                // 但由于我们最终是计算 aLength - index，只要index指向的是一个有效的“分界点”即可。
                // 更严谨的做法是找到第一个等于target的元素的索引，但对于本问题，
                // Arrays.binarySearch返回的任何一个target的索引，其左侧都是小于target的，其右侧（包括它自己）都是大于等于target的。
                // 因此，如果index >= 0，它已经是大于等于target的第一个元素（或其中之一）的索引。
            }

            // aLength - index 即为数组a中大于或等于target的元素的数量
            result.add(aLength - index);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arrA = {1, 2, 3, 4, 5};
        int[] arrB = {6, 5, 4, 3, 2};
        System.out.println("Optimized result: " + giantArmyOptimized(arrA, arrB)); // 预期输出: [0, 1, 2, 3, 4]
    }
}

Optimized result: [0, 1, 2, 3, 4]

[1 2 3 4 5]
                (number of elements >= 6) = 0
         x      (number of elements >= 5) = 1
       x x      (number of elements >= 4) = 2
     x x x      (number of elements >= 3) = 3
   x x x x      (number of elements >= 2) = 4
 x x x x x      (number of elements >= 1) = 5
 x x x x x      (number of elements >= 0) = 5