时间戳

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

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

问题描述

我有一个基于 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;
    }
}

`

如果我们正在寻找的值低于第一个百分位，它也应该是第一个百分位。如果我们正在寻找的值高于第 100 个百分位，它也应该是第 100 个百分位。

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

标签： javasearchbinary-searchpercentile

解决方案

我看到可以快速改进的一件简单的事情是将末尾的 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;
}

推荐阅读