逆序对计数分治算法实现结果错误，求排查逻辑与代码缺陷

核心错误点 #

• 排序参数错误：Java 标准库Arrays.sort(long[] a, int fromIndex, int toIndex)的作用范围是左闭右开区间，你当前代码中Arrays.sort(arr, l, r)的写法会漏掉下标为r的元素，导致递归返回的子数组并未完全排序，后续基于有序子数组的二分查找逻辑完全失效。
• 二分查找逻辑缺陷：Arrays.binarySearch在数组内存在多个匹配元素时，不会保证返回第一个匹配元素的下标，重复元素场景下计算出的跨子数组逆序对数量会出现偏差。
• （可选优化）当前实现每层递归调用Arrays.sort的时间复杂度为O(nlogn)，整体时间复杂度为O(n(logn)²)，可以优化为归并排序的合并逻辑，将时间复杂度降到O(nlogn)。

修正后代码 #

import java.util.Arrays;

static long inversionCount(long arr[], long N){
    return solve(0, (int)N-1, arr);
}

static long solve(int l, int r, long[] arr){
    if(l >= r) return 0;
    
    int mid = l+(r-l)/2;
    
    long countL = solve(l, mid, arr);
    long countR = solve(mid+1, r, arr);
    
    long countM = 0;
    
    // 自行实现二分，保证返回右半数组中第一个大于等于目标值的位置
    for(int idx = l; idx <= mid; idx++){
        long target = arr[idx];
        int left = mid + 1, right = r + 1;
        while(left < right) {
            int m = left + (right - left)/2;
            if(arr[m] >= target) {
                right = m;
            } else {
                left = m + 1;
            }
        }
        countM += left - (mid + 1);
    }
    
    // 修正排序的右边界参数
    Arrays.sort(arr, l, r + 1);
    
    return countM + countL + countR;
}

内容的提问来源于stack exchange，提问作者Akash Yadav