优化双数组比较性能：排序与二分查找的高效实践

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

public class ArrayComparison {
    /**
     * 传统嵌套循环方法，计算数组a中大于等于b中每个元素的个数
     * @param a 数组a
     * @param b 数组b
     * @return 结果列表
     */
    public static List<Integer> giantArmyNaive(int a[], int b[]) {
        List<Integer> list = new ArrayList<>();
        // 特殊情况处理：如果a只有一个元素且为0，则直接返回[0]
        // 实际应用中，此条件可能需要根据具体业务逻辑调整或移除
        if (a.length == 1 && a[0] == 0) {
            list.add(0);
            return list;
        }

        for (int i = 0; i < b.length; i++) {
            int count = 0; // 每次循环b的元素时重置计数器
            for (int j = 0; j < a.length; j++) {
                if (a[j] >= b[i]) {
                    count++;
                }
            }
            list.add(count);
        }
        return list;
    }
}

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

public class ArrayComparisonOptimized {

    /**
     * 优化后的方法，使用排序和二分查找计算数组a中大于等于b中每个元素的个数
     * @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 & 3 & 4: 遍历b，对每个元素在a中进行二分查找并计算
        for (int b_element : b) { // O(M) 次循环
            int index = Arrays.binarySearch(a, b_element); // O(log N)

            // 如果二分查找结果为负，说明b_element不存在于a中
            // 此时index = -(插入点) - 1
            // 真实的插入点 (即第一个大于b_element的元素的索引) = -index - 1
            if (index < 0) {
                index = -index - 1;
            }
            // 此时index代表了a中第一个大于或等于b_element的元素的索引
            // 那么，从这个索引到数组末尾的所有元素都符合条件
            result.add(aLength - index);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        int[] b = {6, 5, 4, 3, 2};
        System.out.println("原始数组 a: " + Arrays.toString(a));
        System.out.println("原始数组 b: " + Arrays.toString(b));
        List<Integer> optimizedResult = giantArmyOptimized(a, b);
        System.out.println("优化方法计算结果: " + optimizedResult); // 输出: [0, 1, 2, 3, 4]

        // 验证传统方法（如果需要）
        // System.out.println("传统方法计算结果: " + giantArmyNaive(new int[] {1, 2, 3, 4, 5}, new int[] {6, 5, 4, 3, 2}));
    }
}

数组 a: [1, 2, 3, 4, 5]
索引:     0  1  2  3  4
aLength = 5

当 b_element = 6:
  Arrays.binarySearch(a, 6) 返回 -6 (表示应插入到索引5)
  index = -(-6) - 1 = 5
  结果 = aLength - index = 5 - 5 = 0 (没有元素 >= 6)

当 b_element = 5:
  Arrays.binarySearch(a, 5) 返回 4 (5在索引4)
  index = 4
  结果 = aLength - index = 5 - 4 = 1 (元素: 5)

当 b_element = 4:
  Arrays.binarySearch(a, 4) 返回 3 (4在索引3)
  index = 3
  结果 = aLength - index = 5 - 3 = 2 (元素: 4, 5)

当 b_element = 3:
  Arrays.binarySearch(a, 3) 返回 2 (3在索引2)
  index = 2
  结果 = aLength - index = 5 - 2 = 3 (元素: 3, 4, 5)

当 b_element = 2:
  Arrays.binarySearch(a, 2) 返回 1 (2在索引1)
  index = 1
  结果 = aLength - index = 5 - 1 = 4 (元素: 2, 3, 4, 5)

当 b_element = 1:
  Arrays.binarySearch(a, 1) 返回 0 (1在索引0)
  index = 0
  结果 = aLength - index = 5 - 0 = 5 (元素: 1, 2, 3, 4, 5)

当 b_element = 0 (假设):
  Arrays.binarySearch(a, 0) 返回 -1 (表示应插入到索引0)
  index = -(-1) - 1 = 0
  结果 = aLength - index = 5 - 0 = 5 (元素: 1, 2, 3, 4, 5)