有序列表A包含1和一些素数。那么，对于列表中的每一项p< q，第k小的分数p/q是多少?以整数数组的形式返回答案，其中answer[0] = p和answer[1] = q。并算法的时间复杂度小于O(N^2)

问题简介：有序列表A包含1和一些素数。那么，对于列表中的每一项p< q，第k小的分数p/q是多少?以整数数组的形式返回答案，其中answer[0] = p和answer[1] = q。并算法的时间复杂度小于O(N^2)

要求：
(a)设计一个时间复杂度优于O(n^2)的算法，其中n是数组a的大小，这意味着不列出所有的分数，代价为O(n^2)。对算法进行了分析，并使用顺序表示法给出了结果。
(b)在Python中以函数的形式实现算法:
def kth_smallest_fraction (A, k):

#include<iostream>
#include<vector>
using namespace std;
class Solution{            //二分查找       
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) 
    {
        double left = 0, right = 1.0, mid;
        int p = 0;
        int q = 1;
        int Asize = A.size();
        int count; 
        while (true) 
        {
            double mid = (left + right) / 2.0;
            count = 0; 
            p = 0;
            for (int i = 0, j = i+1; i < Asize; ++i) 
            {
                while (j < Asize && mid < (double)A[i]/(double)A[j]  )
                {
                    ++j;
                }
                count += Asize - j;     //记录在 mid 之前数的个数
                if (j < Asize && (double)p/(double)q < (double)A[i]/(double)A[j])   //记录此时在mid之前的最大的 p / q
                {
                    p = A[i];
                    q = A[j];
                }
            }
            if (count == K)         //若相等就返回此时的p q
            {
                return {p, q};
            }
            else if (count < K)     //若 count < K 就缩小区间为[mid,right]
            {
                left = mid;
            }
            else                    //若 count > K 就缩小区间为[left,mid]
            {
                right = mid;
            }
        }
    }
};