如何改进这种Java二进制搜索方法以找到给定值的最佳百分位数？

Question

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

Double[] 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, 5429.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, 5785.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, 6141.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, 6942.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;
    }
}

`

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

顺便说一句 - 我知道Arrays.binarysearch（..）方法。

Answer 1

我看到的一个简单的事情是可以快速改进的是将最后的If块移动到开头，这样它就不会在那些特定情况下进入循环，使其稍微快一些。

以下是它的样子。

编辑：我通过将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;
}