Casey

二分

最近更新：2025-02-17 | 字数总计：862 | 阅读估时：3分钟 | 阅读量：次

整数二分

经典场景

首先来看整数二分最经典的应用

Q. 从升序的数组 nums 中找到值为 x 的点，并返回其下标，若不存在，返回 -1。

为了解决这个问题，我们可以将区间从中间一分为二，判断中点是否是 x，若不是，再在子区间中查找，代码如下。

int binsearch(vector<int> nums, int target) {
  int left = 0, right = nums.size() - 1, mid;
  while (left < right) {
    mid = (left + right) >> 1;
    if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      break;
    }
  }
  if (nums[mid] == target) {
    return mid;
  } else {
    return -1;
  }
}

拓展场景

将这个问题拓展一下。

Q. 从升序数组 nums 中找到值大于等于 x 下标最小的点。

对于这个问题，也可以使用二分进行求解。基本思路依然为检查 nums[mid] 和 x 之间的关系：若 nums[mid] >= x 那么下标最小的点一定为 mid 本身或其左侧，否则下标最小的点一定处在 mid 右侧。代码如下。

int binsearch(vector<int> nums, int target) {
  int left = 0, right = nums.size(), mid;
  while (left < right) {
    mid = (left + right) >> 1;
    if (nums[mid] >= x) {
      right = mid;
    }
    else {
      left = mid + 1;
    }
  }
  return left;
}

这里有两个小细节：1. right 初始时取到 nums.size()，因为存在 nums 数组中所有的数均小于 x 的情况，此时的大于等于 x 的最小的点应处于 nums.size()。2. 根据分析，我们将区间划分为 [left, mid] 或 [mid + 1, right] 两部分，我们在取中点时应取 (left + right) / 2，即下取整，可以使这两个区间不会存在 mid == right 或是 mid + 1 == left 的情况，避免死循环。

类似的，有另一个拓展的问题。

Q. 从升序数组 nums 中找到值小于等于 x 下标最大的点。

这里可以类比上面的分析，得到下面的代码。

int binsearch(vector<int> nums, int target) {
  int left = 0, right = nums.size() - 1, mid;
  while (left < right) {
    mid = (left + right + 1) >> 1;
    if (nums[mid] <= x) {
      left = mid
    }
    else {
      right = mid - 1;
    }
  }
  return left;
}

这里同样需要注意几个小细节：1. nums 数组初始从 1 开始存储数字，left 初始置为 0，应对数组中所有数均大于 x 的情况。2.根据区间划分，此时中点应该取 mid = (left + right + 1) / 2 以避免死循环。

类似的，我们可以很简单的类推得到下面几个问题的代码。

Q. 从升序数组 nums 中找到值大于 x 下标最小的点。

Q. 从升序数组 nums 中找到值小于 x 下标最大的点。

Q. 从降序数组 nums 中找到值小于（等于） x 下标最小的点。

Q. 从降序数组 nums 中找到值大于（等于） x 下标最大的点。

浮点二分

浮点二分并不存在区间端点问题，只需要控制精度。
下面是浮点二分最经典的一个应用场景。

Q. 求 sqrt(x)（x >= 1），保留小数点后四位。

对于这个问题，我们可以利用二分快速对解的区间进行逼近，从而得到近似解，代码如下。

double binsqrt(double x) {
  double eps = 1e-6;
  double left = 1, right = x, mid;
  while (right - left >= eps) {
    mid = (left + right) / 2;
    if (mid * mid > x) {
      right = mid;
    }
    else if (mid * mid < x) {
      left = mid;
    }
    else {
      return mid;
    }
  }
  return left;
}

上面代码中的 eps 用于控制精度，一般设置为题目要求精度再低两个数量级。

2025-02-17 该篇文章被 Casey 打上标签: 算法 C++ 归为分类: 学习