Function CalcSampleQuantileBinarySearch

catboost/libs/helpers/quantile.cpp:18–77

}

static double CalcSampleQuantileBinarySearch(
    TConstArrayRef<float> sampleRef,
    TConstArrayRef<float> weightsRef,
    const double alpha
) {
    constexpr int BINARY_SEARCH_ITERATIONS = 100;

    const double totalWeight = Accumulate(weightsRef, 0.0);
    const double needWeight = totalWeight * alpha;

    const auto minMaxSamples = MinMaxElement(sampleRef.begin(), sampleRef.end());
    double lQ = *minMaxSamples.first - DBL_EPSILON;
    double rQ = *minMaxSamples.second;

    const size_t sampleSize = sampleRef.size();
    TVector<TValueWithWeight> elements;
    elements.yresize(sampleSize);
    for (auto i : xrange(sampleSize)) {
        elements[i] = {sampleRef[i], weightsRef[i]};
    }
    /*
     * We will support the following invariant:
     * total weight of elements with sample values <= lQ is strictly less than needWeight
     * total weight of elements with sample values <= rQ is greater or equal than needWeight
     * elements with indices < l are less or equal than q
     * elements with indices > r are greater than q
     */
    int l = 0, r = sampleSize;
    double collectedLeftWeight = 0;
    for (auto it : xrange(BINARY_SEARCH_ITERATIONS)) {
        Y_UNUSED(it);
        const double q = (lQ + rQ) / 2;
        auto partitionIt = std::partition(
            elements.begin() + l,
            elements.begin() + r,
            [q](const TValueWithWeight& element) {
                return element.Value <= q;
            }
        );
        const double partitionLeftWeight = Accumulate(
            elements.begin() + l,
            partitionIt,
            0.0,
            [](double sum, const TValueWithWeight& element) {
                return sum + element.Weight;
            }
        );
        const int partitionPoint = partitionIt - elements.begin();

        if (collectedLeftWeight + partitionLeftWeight < needWeight - DBL_EPSILON) {
            l = partitionPoint;
            lQ = q;
            collectedLeftWeight += partitionLeftWeight;
        } else {
            r = partitionPoint;
            rQ = q;
        }
    }