Java中降序数组二分查找统计GPA时返回负值的问题

• 问题根源：降序数组的首尾出现位置判断逻辑错误，导致firstIndex和lastIndex取值不符合预期，最终计算结果为负值。
• 具体错误点：
  1. findFirstOccurrenceDescending方法中，判断第一个出现位置的条件错误，应检查当前元素左侧元素是否大于目标值（符合降序数组特性），而非右侧元素。
  2. findLastOccurrenceDescending方法中，判断最后一个出现位置的条件错误，应检查当前元素右侧元素是否小于目标值，而非左侧元素。

修正后的完整代码 #

public class Main {

    public static void main(String args[]){
        String path = args[0];
        Student[] Stdnt= Student.readCSV(path).clone();
        double[] GpaArray= new double[Stdnt.length];

        // 修正笔误：将Ogrenciler改为Stdnt
        for(int i=0 ; i<Stdnt.length;i++){
            GpaArray[i] = Stdnt[i].getGPA();
        }
        int sayi = countOccurrences(GpaArray, 3.02);
        System.out.println(sayi);
    }

    public static int countOccurrences(double[] arr, double x) {
        int firstIndex;
        int lastIndex;

        if (arr[0] <= arr[arr.length - 1]) {
            // 升序数组
            firstIndex = findFirstOccurrence(arr, x, 0, arr.length - 1);
            lastIndex = findLastOccurrence(arr, x, 0, arr.length - 1);
        } else {
            // 降序数组
            firstIndex = findFirstOccurrenceDescending(arr, x, 0, arr.length - 1);
            lastIndex = findLastOccurrenceDescending(arr, x, 0, arr.length - 1);
        }

        if (firstIndex == -1) {
            return 0;
        }

        return lastIndex - firstIndex + 1;
    }

    public static int findFirstOccurrence(double[] arr, double x, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;

        if ((mid == 0 || arr[mid - 1] < x) && arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            return findFirstOccurrence(arr, x, mid + 1, right);
        } else {
            return findFirstOccurrence(arr, x, left, mid - 1);
        }
    }

    public static int findLastOccurrence(double[] arr, double x, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;

        if ((mid == arr.length - 1 || arr[mid + 1] > x) && arr[mid] == x) {
            return mid;
        } else if (arr[mid] > x) {
            return findLastOccurrence(arr, x, left, mid - 1);
        } else {
            return findLastOccurrence(arr, x, mid + 1, right);
        }
    }

    public static int findFirstOccurrenceDescending(double[] arr, double x, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;

        // 修正：判断左侧元素是否大于目标值（降序数组中，第一个出现的x左边元素更大）
        if ((mid == 0 || arr[mid - 1] > x) && arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            // x比当前元素大，在左侧查找
            return findFirstOccurrenceDescending(arr, x, left, mid - 1);
        } else {
            // x比当前元素小，在右侧查找
            return findFirstOccurrenceDescending(arr, x, mid + 1, right);
        }
    }

    public static int findLastOccurrenceDescending(double[] arr, double x, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;

        // 修正：判断右侧元素是否小于目标值（降序数组中，最后一个出现的x右边元素更小）
        if ((mid == arr.length - 1 || arr[mid + 1] < x) && arr[mid] == x) {
            return mid;
        } else if (arr[mid] > x) {
            // x比当前元素小，在右侧查找
            return findLastOccurrenceDescending(arr, x, mid + 1, right);
        } else {
            // x比当前元素大，在左侧查找
            return findLastOccurrenceDescending(arr, x, left, mid - 1);
        }
    }
}

额外说明 #

• 同时修正了main方法中的笔误：将Ogrenciler.length改为Stdnt.length，避免数组遍历错误。
• 修正后的降序查找逻辑匹配数组特性，能够正确定位目标值的首尾出现位置，从而计算出正确的出现次数。

内容的提问来源于stack exchange，提问作者Yusuf Yigit