二分答案

概述

二分答案即利用二分查找来得到答案，一般情况下，左边界 $left$ 是 $0$ 或者 $1$；右边界 $right$ 则视题目条件而定，取一个很大的数，然后利用二分查找的思想，来找到答案。

二分答案的要求

如果题目能够使用二分答案的思想来解决，那么 $[left, right]$ 范围内，要满足二段性，即对 $[left, res]$ 满足条件 $A$，而 $(res, right]$ 不满足条件 $A$，并且 res 的取值范围是连续的。

适用情况

如果题目要求满足 xxx 条件下的最大值或者最小值，就可以考虑二分答案，特别的，如果题目要求最小化的最大值或者最大化的最小值，那么要首先考虑使用二分答案。

例题

2517. 礼盒的最大甜蜜度 (Medium)

class Solution {
  public:
    int Bsearch(int target, vector<int> &price, int left) {
        int right = price.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (price[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    bool Check(int mid, vector<int> &price, int k, int n) {
        int start = 0;
        for (int i = 0; i < k - 1; ++i) {
            start = Bsearch(price[start] + mid, price, start);
            // cout << start << " start\n";
            if (start >= n) { 
                return false;
            }
        }
        return true;
    }
    int maximumTastiness(vector<int> &price, int k) {
        // 先排序，然后考虑是二分答案还是双指针
        sort(price.begin(), price.end());
        // 二分答案，时间复杂度为 log(price[i]) * k * log(n)
        int n = price.size();
        int left = 0, right = (price[n - 1] - price[0]) / (k - 1) + 1; // 先看看 k 行不行，不行就改成 2
        while (left < right) {
            // 左闭右开
            int mid = left + (right - left) / 2;
            if (Check(mid, price, k, n)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }
};