二分查找法：假设输入一个值0.6，为了定位其在0~1之间的位置，通过与（0,1）的中间值0.5可知，0.6在（0.5,1）的区间内，又进行0.6与（0.5,1）区间的中间值0.75比较可知，0.6在（0.5,0.75）的区间之间。在有限的精确度的条件下，通过有限次重复以上过程最终会找到0.6的位置。
LeetCode题目：
一个已排序好的表 A，其包含 1 和其他一些素数. 当列表中的每一个 p<q 时，我们可以构造一个分数 p/q 。
那么第 k 个最小的分数是多少呢? 以整数数组的形式返回你的答案, 这里 answer[0] = p 且 answer[1] = q.
示例:
输入: A = [1, 2, 3, 5], K = 3
输出: [2, 5]
解释:
已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3.
很明显第三个最小的分数是 2/5.
输入: A = [1, 7], K = 1 输出: [1, 7]来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-th-smallest-prime-fraction
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
实现代码：
输入：[1,3,5,7] K=5
// testDPfound.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include<vector>
#include <iostream>
using namespace std;
vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
double left = 0.0;
double right = 1.0;
int n = A.size();
while (left < right) {
double mid = (right + left) / 2.0;
int cnt = 0;
cout << "------------------------------------------------" << endl;
cout << '\n'<<" 中间参考值 mid:" << mid << " 初始化：cnt:"
<<cnt<<'\n'<<endl;
vector<int> maxi = { 0, 1 };
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && A[i] >= mid * A[j]) {
cout <<" A[i]/A[j] >= mid A["<<i<<"]/A["<<j<<"]:"<< A[i]
<< '/' << A[j] << endl; j++;
}
cnt += n - j;
cout<<" cnt:" << cnt<<endl;
if (j < n && maxi[0] * A[j] < A[i] * maxi[1])
{
cout << " maxi[0] /maxi[1]< A[i] /A[j] A[" << i << "]/A[" << j
<<"]:" << A[i] << '/' << A[j] << endl;
maxi = { A[i], A[j] };
cout << '\n'<<" 当前刚符合小于mid值，即在分子A[i]固定时分母A[j]"
<<"刚刚使 A[i]/A[j] < mid，maxi = {A[" << i << "],A[" << j << "]}:"
<< A[i] << ',' << A[j] <<'\n'<< endl;
cout << ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>" << endl;
}
}
if (cnt == K) return maxi;
if (cnt < K) left = mid;
else right = mid;
}
return {};
}
int main()
{
vector<int>A = { 1,3,5,7 };
vector<int>result=kthSmallestPrimeFraction(A, 5);
cout <<'\n'<< "result:" << result[0] << ' ' << result[1] << endl;
return 0;
}
//原代码：https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/solution/er
//-fen-cha-zhao-dp-fu-za-du-ya-suo-by-rocky-23/
结果：
------------------------------------------------
中间参考值 mid:0.5 初始化：cnt:0
A[i]/A[j] >= mid A[0]/A[0]:1/1
cnt:3
maxi[0] /maxi[1]< A[i] /A[j] A[0]/A[1]:1/3
当前刚符合小于mid值，即在分子A[i]固定时分母A[j]刚刚使 A[i]/A[j] < mid，maxi =
{A[0],A[1]}:1,3
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
A[i]/A[j] >= mid A[1]/A[1]:3/3
A[i]/A[j] >= mid A[1]/A[2]:3/5
cnt:4
maxi[0] /maxi[1]< A[i] /A[j] A[1]/A[3]:3/7
当前刚符合小于mid值，即在分子A[i]固定时分母A[j]刚刚使 A[i]/A[j] < mid，maxi =
{A[1],A[3]}:3,7
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
A[i]/A[j] >= mid A[2]/A[3]:5/7
cnt:4
cnt:4
------------------------------------------------
中间参考值 mid:0.75 初始化：cnt:0
A[i]/A[j] >= mid A[0]/A[0]:1/1
cnt:3
maxi[0] /maxi[1]< A[i] /A[j] A[0]/A[1]:1/3
当前刚符合小于mid值，即在分子A[i]固定时分母A[j]刚刚使 A[i]/A[j] < mid，maxi =
{A[0],A[1]}:1,3
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
A[i]/A[j] >= mid A[1]/A[1]:3/3
cnt:5
maxi[0] /maxi[1]< A[i] /A[j] A[1]/A[2]:3/5
当前刚符合小于mid值，即在分子A[i]固定时分母A[j]刚刚使 A[i]/A[j] < mid，maxi =
{A[1],A[2]}:3,5
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
A[i]/A[j] >= mid A[2]/A[2]:5/5
cnt:6
maxi[0] /maxi[1]< A[i] /A[j] A[2]/A[3]:5/7
当前刚符合小于mid值，即在分子A[i]固定时分母A[j]刚刚使 A[i]/A[j] < mid，maxi =
{A[2],A[3]}:5,7
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
A[i]/A[j] >= mid A[3]/A[3]:7/7
cnt:6
------------------------------------------------
中间参考值 mid:0.625 初始化：cnt:0
A[i]/A[j] >= mid A[0]/A[0]:1/1
cnt:3
maxi[0] /maxi[1]< A[i] /A[j] A[0]/A[1]:1/3
当前刚符合小于mid值，即在分子A[i]固定时分母A[j]刚刚使 A[i]/A[j] < mid，maxi =
{A[0],A[1]}:1,3
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
A[i]/A[j] >= mid A[1]/A[1]:3/3
cnt:5
maxi[0] /maxi[1]< A[i] /A[j] A[1]/A[2]:3/5
当前刚符合小于mid值，即在分子A[i]固定时分母A[j]刚刚使 A[i]/A[j] < mid，maxi =
{A[1],A[2]}:3,5
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
A[i]/A[j] >= mid A[2]/A[2]:5/5
A[i]/A[j] >= mid A[2]/A[3]:5/7
cnt:5
cnt:5
result:3 5
解释：
mid=0.5
i=0时，分子1，分母[3,5,7]满足条件，分子/分母<mid，数量3。maxi{1,3}
i=1时，分子3，分母[7]满足条件，分子/分母<mid，数量1。maxi{3,7}
i=2时，分子5，分母没有满足条件，数量0。保持maxi{1,3}
i=3时，分子7，分母没有满足条件，数量0。保持maxi{1,3}
总共小于mid的数量：cnt=3+1+0+0=4，不符合条件,cnt!=K
mid=0.75
i=0时，分子1，分母[3,5,7]满足条件，分子/分母<mid，数量3。maxi{1,3}
i=1时，分子3，分母[5,7]满足条件，分子/分母<mid，数量2。maxi{3,5}
i=2时，分子5，分母[7]满足条件，分子/分母<mid,数量1。保持maxi{5,7}
i=3时，分子7，分母没有满足条件，数量0。保持maxi{5,7}
总共小于mid的数量：cnt=3+2+1+0=6，不符合条件,cnt!=K
mid=0.625
i=0时，分子1，分母[3,5,7]满足条件，分子/分母<mid，数量3。maxi{1,3}
i=1时，分子3，分母[5,7]满足条件，分子/分母<mid，数量2。maxi{3,5}
i=2时，分子5，分母没有满足条件，数量0。保持maxi{3,5}
i=3时，分子7，分母没有满足条件，数量0。保持maxi{3,5}
总共小于mid的数量：cnt=3+2+0+0=5，符合条件,cnt==K
返回结果，刚刚满足分子/分母<mid，数量为5，分子/分母=3/5.
心得：之前直接使用全部遍历，然后在降序排序，再选择第K个，然后再遍历查找原本的分子分母（原输入都是质数，没有重复），然后导致LeetCode的超时，小看了算法的精妙。
原代码解释答案作者：rocky-23
链接：https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/solution/er-fen-cha-zhao-dp-fu-za-du-ya-suo-by-rocky-23/