#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;
}
}
}
};