高效搜索与参数空间探索
二分查找是一种在 **有序数组** 中查找特定元素的高效搜索算法。它通过不断将搜索区间减半来快速定位目标值，时间复杂度为 O(log n)。
目标： 在下面的有序数组中查找数字 42。
1. 初始化左右指针：low = 0，high = n-1
2. 当 low <= high 时循环:
a. 计算中间索引：mid = low + (high - low) / 2
b. 比较 array[mid] 与 目标值:
- 如果 array[mid] == target，找到！返回 mid。
- 如果 array[mid] < target，目标在右侧，更新 low = mid + 1。
- 如果 array[mid] > target，目标在左侧，更新 high = mid - 1。
3. 如果循环结束仍未找到，表示目标值不存在，返回 -1。
请点击“下一步”开始演示。
二分答案是二分思想的一种扩展应用，它并不直接在数据索引上进行二分，而是在 **答案的可能取值范围** 内进行二分搜索。前提是问题具有 **单调性**，即存在一个判定函数 check(x)，使得当 x 增大（或减小）时，check(x) 的结果会从 false 变为 true（或反之），且一旦变化就不再变回。
目标： 找到满足某个条件 check(x) 的最小（或最大）的 x。
示例场景： 假设我们要找到满足 check(x) == true 的 **最小** x，且答案范围在 [0, 100] 之间。假设 check(x) 当 x >= 60 时为 true，否则为 false。
1. 确定答案的可能范围 [l, r]。
2. 当 l < r 时循环 (寻找最小值模板):
a. 计算中间值：mid = l + (r - l) / 2
b. 调用判定函数 check(mid):
- 如果 check(mid) 为 true (mid 可能是一个解，尝试更小的)，更新 r = mid。
- 如果 check(mid) 为 false (mid 太小了，需要更大的)，更新 l = mid + 1。
3. 循环结束，l (或 r) 即为所求的最小答案。
注意： 寻找最大值的模板略有不同 (通常是 l = mid, r = mid - 1 配合 mid = l + (r - l + 1) / 2)。
请点击“下一步”开始演示。
核心在于问题答案具有单调性，可以通过 check(mid) 函数判断当前尝试的答案 mid 是否可行，并以此缩小答案范围。
关键： 能否设计出一个 check(potential_answer) 函数，判断该答案是否可行/满足要求，并且这个可行性随 potential_answer 变化是单调的。
| 特点 | 二分查找 | 二分答案 |
|---|---|---|
| 搜索对象 | 数据本身 (在有序序列中的位置) | 问题的解 (答案的可能值) |
| 搜索空间 | 数组的索引范围 [0, n-1] |
答案的可能取值范围 [min_val, max_val] |
| 核心操作 | 比较 array[mid] 与 target |
调用判定函数 check(mid) |
| 前提条件 | 数据序列有序 | 答案的可行性具有单调性 |
| 目标 | 找到目标值的位置或确定不存在 | 找到满足条件的最小/最大解 |
| 时间复杂度 | O(log n) | O(log(Range) * Tcheck)，其中 Tcheck 是判定函数的时间复杂度 |
mid 的方式最能避免整数溢出问题（假设 low 和 high 都很大）？mid = (low + high) / 2mid = low + (high - low) / 2mid = high - (high - low) / 2mid = (low + high) >> 1 (右移一位)check(mid) 通常应该判断什么？mid？mid？mid？mid？给定一个 **升序** 排列的整数数组 nums 和一个目标值 x，请找出数组中最后一个小于或等于 x 的元素的 **下标**。如果数组中不存在这样的元素，返回 -1。
例如：nums = [2, 5, 5, 7, 8, 10, 12], x = 6, 应返回 2 (对应元素 5)。
nums = [2, 5, 5, 7, 8, 10, 12], x = 1, 应返回 -1。
假设有一个单调递增函数 f(v)（即当 v 增大时，f(v) 的值不会减小）。你需要找到 **最小** 的整数 v（在某个给定范围 [min_v, max_v] 内），使得 f(v) >= K，其中 K 是一个给定的阈值。
你需要实现一个函数 findMinV(min_v, max_v, K, f)，其中 f 是一个可以调用的函数对象或 lambda 表达式，代表判定函数 f(v)。
low <= high 还是 low < high) 和区间更新 (mid+1, mid-1, mid)。check(mid) 判定函数，并根据其结果正确更新答案范围 l 和 r。注意不同模板（求最小/最大）的细节差异。选择关键： 当问题直接要求在有序数据中“查找”时，优先考虑二分查找。当问题要求“求解最优值”（如最大、最小）且该最优值对应的可行性具有单调性时，考虑二分答案。
#include <vector>
#include <iostream>
// 函数：二分查找
// 参数：nums - 有序整数向量, target - 要查找的目标值
// 返回：目标值在数组中的索引，如果不存在则返回 -1
int binarySearch(const std::vector<int>& nums, int target) {
int low = 0; // 左边界索引
int high = nums.size() - 1; // 右边界索引
// 当左边界小于等于右边界时，继续查找
while (low <= high) {
// 计算中间索引，使用这种方式防止 low + high 溢出
int mid = low + (high - low) / 2;
// 检查中间元素是否是目标值
if (nums[mid] == target) {
return mid; // 找到目标值，返回索引
}
// 如果中间元素小于目标值，说明目标值在右半部分
else if (nums[mid] < target) {
low = mid + 1; // 移动左边界到 mid 右侧
}
// 如果中间元素大于目标值，说明目标值在左半部分
else {
high = mid - 1; // 移动右边界到 mid 左侧
}
}
// 循环结束，未找到目标值
return -1;
}
// --- 示例用法 ---
// int main() {
// std::vector<int> sorted_array = {2, 5, 8, 12, 16, 23, 38, 42, 56, 72};
// int target_value = 42;
// int index = binarySearch(sorted_array, target_value);
//
// if (index != -1) {
// std::cout << "元素 " << target_value << " 在索引 " << index << " 处找到。" << std::endl;
// } else {
// std::cout << "元素 " << target_value << " 未在数组中找到。" << std::endl;
// }
// return 0;
// }
#include <vector>
#include <functional> // 需要包含 functional 头文件来使用 std::function
#include <iostream>
// 函数：二分答案 - 查找满足条件的最小值
// 参数：low_bound - 答案的下界, high_bound - 答案的上界
// check - 判定函数 (lambda 或函数指针)，输入一个可能的答案 mid，返回 bool
// 返回：满足 check(ans) == true 的最小整数 ans
// 注意：此模板适用于 check 函数具有 [false, false, ..., true, true] 的单调性
long long findMinAnswer(long long low_bound, long long high_bound,
const std::function<bool(long long)>& check) {
long long l = low_bound;
long long r = high_bound;
long long ans = high_bound + 1; // 初始化为一个不可能的较大值
while (l <= r) {
long long mid = l + (r - l) / 2;
if (check(mid)) { // 如果 mid 满足条件
ans = mid; // 记录当前可能的最小答案
r = mid - 1; // 尝试在左侧寻找更小的答案
} else { // 如果 mid 不满足条件
l = mid + 1; // 必须增大答案，移动左边界
}
}
// 如果 high_bound + 1 从未被改变，意味着没有找到解（根据题目定义可能返回-1或边界值）
// 这里返回的是找到的满足条件的最小值，或者如果一个都没找到，就返回 high_bound + 1
// 实际应用中可能需要根据题目调整返回值
return ans;
}
// 函数：二分答案 - 查找满足条件的最大值
// 参数：low_bound - 答案的下界, high_bound - 答案的上界
// check - 判定函数 (lambda 或函数指针)，输入一个可能的答案 mid，返回 bool
// 返回：满足 check(ans) == true 的最大整数 ans
// 注意：此模板适用于 check 函数具有 [true, true, ..., false, false] 的单调性
long long findMaxAnswer(long long low_bound, long long high_bound,
const std::function<bool(long long)>& check) {
long long l = low_bound;
long long r = high_bound;
long long ans = low_bound - 1; // 初始化为一个不可能的较小值
while (l <= r) {
long long mid = l + (r - l) / 2;
if (check(mid)) { // 如果 mid 满足条件
ans = mid; // 记录当前可能的最大答案
l = mid + 1; // 尝试在右侧寻找更大的答案
} else { // 如果 mid 不满足条件
r = mid - 1; // 必须减小答案，移动右边界
}
}
return ans;
}
// --- 示例用法 (查找满足 x*x >= K 的最小 x) ---
// bool check_square(long long x, long long K) {
// // 注意溢出！可能需要使用 __int128 或其他方法处理大数乘法
// // 这里简化处理，假设不会溢出 long long
// return x * x >= K;
// }
//
// int main() {
// long long K = 100;
// long long min_v = 0;
// long long max_v = 100; // 假设答案范围
//
// // 使用 lambda 表达式作为判定函数
// long long result = findMinAnswer(min_v, max_v,
// [K](long long mid) { return mid * mid >= K; });
//
// if (result <= max_v) { // 检查是否找到了有效解
// std::cout << "满足 mid*mid >= " << K << " 的最小整数 mid 是: " << result << std::endl;
// } else {
// std::cout << "在范围内未找到满足条件的 mid。" << std::endl;
// }
//
// return 0;
// }
#include <vector>
#include <iostream>
// 函数：查找最后一个小于等于 x 的元素的下标
// 参数：nums - 升序排列的整数向量, x - 目标值
// 返回：最后一个小于等于 x 的元素的下标，如果不存在则返回 -1
int findLastLessEqual(const std::vector<int>& nums, int x) {
int low = 0;
int high = nums.size() - 1;
int ans = -1; // 初始化结果为 -1
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] <= x) {
// 如果 nums[mid] 小于等于 x，它可能是一个候选答案
// 并且我们应该尝试在右侧（更大的索引）寻找可能存在的、同样满足条件的、但位置更靠后的元素
ans = mid; // 记录当前满足条件的下标
low = mid + 1; // 继续向右搜索
} else {
// 如果 nums[mid] 大于 x，说明 mid 及右侧的所有元素都大于 x
// 需要在左侧寻找更小的元素
high = mid - 1;
}
}
return ans; // 返回最后记录的满足条件的下标
}
// --- 示例用法 ---
// int main() {
// std::vector<int> nums1 = {2, 5, 5, 7, 8, 10, 12};
// int x1 = 6;
// std::cout << "Nums: [2, 5, 5, 7, 8, 10, 12], x = 6. Last index <= x: " << findLastLessEqual(nums1, x1) << std::endl; // 应输出 2
//
// std::vector<int> nums2 = {2, 5, 5, 7, 8, 10, 12};
// int x2 = 5;
// std::cout << "Nums: [2, 5, 5, 7, 8, 10, 12], x = 5. Last index <= x: " << findLastLessEqual(nums2, x2) << std::endl; // 应输出 2
//
// std::vector<int> nums3 = {2, 5, 5, 7, 8, 10, 12};
// int x3 = 1;
// std::cout << "Nums: [2, 5, 5, 7, 8, 10, 12], x = 1. Last index <= x: " << findLastLessEqual(nums3, x3) << std::endl; // 应输出 -1
//
// std::vector<int> nums4 = {10, 20, 30};
// int x4 = 50;
// std::cout << "Nums: [10, 20, 30], x = 50. Last index <= x: " << findLastLessEqual(nums4, x4) << std::endl; // 应输出 2
//
// return 0;
// }
#include <functional>
#include <iostream>
#include <algorithm> // for std::min
// 函数：查找满足 f(v) >= K 的最小整数 v
// 参数：min_v - 搜索范围下界, max_v - 搜索范围上界
// K - 阈值
// f - 单调递增（或非递减）的函数对象或 lambda
// 返回：满足 f(v) >= K 的最小整数 v。如果范围内不存在，可能返回 max_v + 1 (或根据具体要求调整)
long long findMinV(long long min_v, long long max_v, long long K,
const std::function<long long(long long)>& f) {
long long l = min_v;
long long r = max_v;
long long ans = max_v + 1; // 初始化为范围外的较大值
// 使用二分答案模板（查找最小值）
while (l <= r) {
long long mid = l + (r - l) / 2;
if (f(mid) >= K) { // 如果 f(mid) 满足条件
ans = mid; // 记录当前可能的最小解
r = mid - 1; // 尝试在左侧寻找更小的解
} else { // 如果 f(mid) 不满足条件 (f(mid) < K)
l = mid + 1; // 必须增大 v，向右搜索
}
}
return ans; // 返回找到的最小 v，如果没找到则为 max_v + 1
}
// --- 示例用法 ---
// // 定义一个单调递增函数 f(v) = v*v
// long long square_func(long long v) {
// // 注意处理可能的溢出，这里简化
// if (v > 3037000499LL) return -1; // 防止 v*v 溢出 long long
// return v * v;
// }
//
// // 定义另一个单调函数 f(v) = 2*v + 5
// long long linear_func(long long v) {
// return 2 * v + 5;
// }
//
// int main() {
// long long K1 = 100;
// long long min_v1 = 0;
// long long max_v1 = 100;
// long long result1 = findMinV(min_v1, max_v1, K1, square_func);
// if (result1 <= max_v1) {
// std::cout << "对于 f(v) = v*v, 满足 f(v) >= " << K1 << " 的最小 v 是: " << result1 << std::endl; // 应是 10
// } else {
// std::cout << "对于 f(v) = v*v, 在 [" << min_v1 << ", " << max_v1 << "] 未找到满足条件的 v。" << std::endl;
// }
//
// long long K2 = 50;
// long long min_v2 = 0;
// long long max_v2 = 30;
// long long result2 = findMinV(min_v2, max_v2, K2, linear_func);
// if (result2 <= max_v2) {
// std::cout << "对于 f(v) = 2*v + 5, 满足 f(v) >= " << K2 << " 的最小 v 是: " << result2 << std::endl; // 2*v+5 >= 50 -> 2v >= 45 -> v >= 22.5 -> 最小整数v=23
// } else {
// std::cout << "对于 f(v) = 2*v + 5, 在 [" << min_v2 << ", " << max_v2 << "] 未找到满足条件的 v。" << std::endl;
// }
//
// return 0;
// }