Description

Submission

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        int n = arr.size();
        double lower = 0, upper = 1;

        double mid;
        while(left < right) {
            mid = (lower + upper) / 2;

            int cnt = 0;
            for(int d: arr) {    // for denominators
                cnt += upper_bound(arr.begin(), arr.end(), mid * d) - arr.begin();
            }

            if(cnt > k) { // mid is too large
                upper = mid;
            } else if(cnt < k) {
                lower = mid;
            } else {
                break;
            }
        }

        vector<int> rets {1, 1};
        for(int d: arr) {    // for denominators
            auto it = upper_bound(arr.begin(), arr.end(), mid * d); // lower_bound and upper_bound are almost interchangeable
            if(it == arr.begin()) continue;
            --it;
            if(abs(rets[0] * 1.0 / rets[1] - mid) > abs(*it * 1.0 / d  - mid)) rets = {*it, d};
        }
        return rets;
    }
};

// for a given number(from the one we set by using binary search)
// traverse all the denominators
// add up the number of suitable enumerators, such that the # of suitable pairs is adequate

// enumerator / denominator <= mid
// enumerator <= mid * denominator