二分猜答案

二分

前后缀分解

lc786

二分查找分数值范围，统计小于等于中间值的分数个数，定位第k小的素数分数并返回

#include <vector>
using namespace std;

class Solution {
private:
vector<int> arr;
int n, a, b;
public:
vector<int> kthSmallestPrimeFraction(vector<int>& _arr, int k) {
arr = _arr;
n = arr.size();
double l = 0, r = 1;
while (true) {
double mid = (l + r) / 2;
int cnt = check(mid);
if (cnt > k) r = mid;
else if (cnt < k) l = mid;
else break;
}
return {a, b};
}
private:
int check(double x) {
int ans = 0;
double large = 0;
for (int i = 0, j = 1; j < n; j++) {
while (arr[i + 1] * 1.0 / arr[j] <= x)
i++;

if (arr[i] * 1.0 / arr[j] <= x) {
ans += i + 1;
if (arr[i] * 1.0 / arr[j] > large) {
a = arr[i];
b = arr[j];
large = arr[i] * 1.0 / arr[j];
}
}
}
return ans;
}
};
核心逻辑：用二分查找定位“第k小的素数分数”，不用暴力枚举所有分数，效率更高

1. 前提：输入数组是从小到大排序的素数，要找的是“两个素数相除（分子在前、分母在后，分子<分母）”中第k小的那个分数（比如数组[2,3,5]，分数有2/3、2/5、3/5，第2小是2/5）

2. 二分查找的是什么？

不直接找分数，而是找“分数的数值大小”。因为所有可能的分数都在 0~1 之间（分子<分母），所以在 [0,1] 区间里二分：

- 每次取中间值 mid ，统计“所有小于等于 mid 的分数有多少个”（用 check 函数算）。

- 如果统计数 >k：说明第k小的分数比 mid 小，缩小右边界；

- 如果统计数 <k：说明第k小的分数比 mid 大，扩大左边界；

- 统计数 ==k：说明 mid 刚好“卡”在第k小的分数上，找到目标。

3. check函数怎么统计？

用“双指针”高效计数（不用两两枚举，避免超时）：

- 固定分母 j ，找最大的分子 i 使得 arr[i]/arr[j] ≤ mid （因为数组有序， i 越大，分数越大）；

- 此时， i+1 就是以 arr[j] 为分母、满足条件的分数个数（分子可以是 arr[0]~arr[i] ）；

- 同时记录这些分数中最大的那个（因为统计数==k时，这个最大分数就是第k小的目标）。