786. 第 K 个最小的素数分数

题目求的是第$k$个最小分数，而这些分数的范围都是$(0,1)$，所以我们可以用二分法来求，初始化$left = 0.0 , right = 1.0$。求第$k$个最小分数，也就是有一个数，小于它的数有$k$个，这$k$个数里的最大的那个数就是第$k$个最小分数了。

所以对于每次求得的$mid$，我们求得小于$mid$的分数的数量，如果等于$k$，则我们找到了答案，如果大于$k$，则$r = mid$，如果小于$k$，则$l = mid$。

疑问1：此二分查找的终止条件是什么？

终止条件是对于某一次$mid$，小于其的分数的数量等于$k$，就终止了。由于每次$mid$都是分数，所以对于序列中的任意两个相邻分数$x和y$，两者之间总能找到一个$mid$。

疑问2：为什么$l$和$r$都赋值为$mid$？

因为现在的二分是按值二分，而不是按照索引二分，而且$mid、l、r$都是浮点数，我们二分的范围其实是$(l,r)$，所以每次缩小后的范围是$(mid,r)$或$(l,mid)$，这样并没有丢失目标解，因为现在$mid$是不符合题意的，所以这样是合理的。

疑问3：为什么$while$条件是$l < r$ ?

因为二分的范围是$(l,r)$，而且$l和r$都是浮点数，所以当$l < r$时，$(l,r)$不是空集，当$l == r$时，$(l,r)$是空集，则结束循环。而且不会出现$l == r$的情况。

代码

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int k) {
        int n = A.size();
        double l = 0.0;
        double r = 1.0;
        while(l < r){
            double mid = (l + r) / 2.0;
            int sum = 0;
            vector<int> res = {0 , 1};
            int j = 0;
            for(int i = 0 ; i<n ; ++i){
                while(j < n && A[i] >= mid * A[j]){
                    ++j;
                }
                sum += n - j; //对于每个mid，求出A[i]为分子且小于mid的分数的数量
                if(j < n && res[0] * A[j] < res[1] * A[i]){
                    res = {A[i] , A[j]}; // 更新为最大分数
                }
            }
            if(sum == k){
                return res;
            }
            else if(sum < k){
                l = mid;
            }
            else r = mid;
        }
        return {};  //不可能出现的情况
    }
};