java - 如何改进 Java 二分搜索方法来找到给定值的最佳百分位？

Question

我有一个基于 X 笔交易的房价百分位值的排序数组:

双[] arr = {2418.0, 2535.0, 2652.0, 2808.0, 2808.0, 2808.0, 2808.0, 2808.0, 2808.0, 3657.0, 3816.0, 4144.0, 5429.0, 542 9.0、5429.0、5429.0、5429.0、5518.0、5518.0、 5518.0、5518.0、5518.0、5607.0、5607.0、5607.0、5607.0、5607.0、5607.0、5696.0、5696.0、5696.0、5696.0、5696.0、5785.0、5 785.0、5785.0、5785.0、5785.0、5874.0、5874.0、5874.0、5874.0、5874.0、5874.0、 5963.0、5963.0、5963.0、5963.0、5963.0、5963.0、6052.0、6052.0、6052.0、6052.0、6052.0、6052.0、6141.0、6141.0、6141.0、6 141.0、6141.0、6141.0、6230.0、6230.0、6230.0、6230.0、6230.0、6319.0、6319.0、 6319.0、6319.0、6319.0、6408.0、6408.0、6408.0、6497.0、6497.0、6497.0、6586.0、6586.0、6645.4、6675.0、6764.0、6853.0、6 942.0、7120.0、7337.3、7924.2、8244.5、8564.0、8840.0、9062.2、9285.9、9492.1、 9717.5、10013.2、10668.4、12034.5、13386.0、22868.0}；

因此，房价的第 1 个百分位数是 2418，房价的第 100 个百分位数是 22868。与百分位数一样，根据输入，某些百分位数可能具有相同的值(如 6141、6408 以及上面示例中的其他内容)。

现在我正在编写一个方法，给定一个房价(不一定在原始 X 交易中)，它将找到它所属的最佳百分位。我编写了这个二分搜索代码，看起来工作正常，但我觉得它可以改进:

`

public static int findRelevantPercentile(Double [] arr, double searchFor){   
    int start = 0;
    int end  = arr.length - 1;
    int middle;
    do{
        middle = (start + end) / 2;
        if (arr[middle] >= searchFor){
            end = middle;
        } else {
            start = middle;
        }
    }while(start + 1 < end);

    if (searchFor >= arr[end]){
        return arr.length;
    } else{
        return start + 1;
    }
}

`

如果我们要查找的值低于第一个百分位数，它也应该是第一个百分位数。如果我们要查找的值高于第 100 个百分位数，那么它也应该是第 100 个百分位数。

顺便说一句 - 我知道 Arrays.binarysearch(..) 方法。

Answer 1

我认为可以快速改进的一个简单的事情是将末尾的 If block 移动到开头，这样它就不会在这些特定情况下进入循环，从而使其速度稍快一些。

这是之后的样子。

编辑:我通过将 DO WHILE 更改为 WHILE 并将中间声明移动到循环内部来清理它，因为它的作用域永远不会离开循环。

public static int findRelevantPercentile(Double [] arr, double searchFor){   
    int start = 0;
    int end  = arr.length - 1;

    if (searchFor >= arr[end]){
        return arr.length;
    }
    while(start + 1 < end) {
        int middle = (start + end) / 2;
        if (arr[middle] >= searchFor){
            end = middle;
        } else {
            start = middle;
        }
    }
    return start + 1;
}