二分查找⚓︎

二分查找（ $\text{Binary Search}$ ）及其变形是一类通过维护单调性并不断缩小搜索区间来定位答案的方法。它既可以用于有序数组中的位置查找，也可以用于答案二分、实数域搜索等问题。

二分查找⚓︎

升序数组中查找大于等于

$target$ 的第一个元素

闭区间左闭右开开区间

C++

int lower_bound(const vector<int> &nums, int target) {
  int left = 0, right = nums.size() - 1;
  while (left <= right) {  // 循环结束时有 L = R + 1
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;  // [mid+1, right]
    } else {
      right = mid - 1;  // [left, mid-1]
    }
  }
  return left;  // return right + 1;
}

C++

int lower_bound(const vector<int> &nums, int target) {
  int left = 0, right = nums.size();
  while (left < right) {  // 循环结束时有 L = R
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;  // [mid+1, right)
    } else {
      right = mid;  // [left, mid)
    }
  }
  return left;  // return right;
}

C++

int lower_bound(const vector<int> &nums, int target) {
  int left = -1, right = nums.size();
  while (left + 1 < right) {  // 循环结束时有 L + 1 = R
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid;  // (mid, right)
    } else {
      right = mid;  // (left, mid)
    }
  }
  return right;  // return left + 1;
}

常见的四种情况转化为二分查找：

$\geq x$ ：使用上述二分查找即可
$\gt x$ ：等价于 $\geq x + 1$ ，对于非整数来说就是偏序中第一个大于 $x$ 的元素
$\lt x$ ：等价于 $(\geq x) - 1$ ，实际上就是第一个 $\geq x$ 的位置左边一个
$\leq x$ ：等价于 $(\gt x) - 1$ ，实际上就是第一个 $\gt x$ 的位置左边一个

std::lower_bound

Return value
Iterator to the first element of the range [first, last) not ordered before value, or last if no such element is found.

Unlike std::binary_search, std::lower_bound does not require operator< or comp to be asymmetric (i.e., a < b and b < a always have different results). In fact, it does not even require value < *iter or comp(value, *iter) to be well-formed for any iterator iter in [first, last).

std::lower_bound 查找第一个"大于等于"目标值的元素位置。

std::upper_bound

Return value
Iterator to the first element of the range [first, last) ordered after value, or last if no such element is found.

For any iterator iter in [first, last), std::upper_bound requires value < *iter and comp(value, *iter) to be well-formed, while std::lower_bound requires *iter < value and comp(*iter, value) to be well-formed instead.

std::upper_bound 查找第一个"大于"目标值的元素位置。

std::binary_search

Return value
true if there is an element in the range [first, last) that is equivalent to value, and false otherwise.

std::binary_search only checks whether an equivalent element exists. To obtain an iterator to that element (if exists), std::lower_bound should be used instead.

std::binary_search 用于判断目标值是否存在于数组中。

利用 std::lower_bound 和 std::upper_bound 可以方便地实现二分查找。并且可以自定义bool函数check(mid) 来检查条件是否满足。
对于左边满足，右边不满足这样的情况，只需要把 check(mid) 改成 !check(mid)。

Tip

查找满足最大化最小值和最小化最大值的题目，可以使用二分枚举答案。

三分查找⚓︎

三分查找的思想类似于二分查找，但它将搜索区间分为三部分，从而在某些情况下可以更快地找到目标值。三分通常用于寻找函数的极值点（最大值或最小值）。

三分

给定一个 $n$ 次多项式 $f(x) = a_n x^n + a_{n-1} x^{n-1} + ... + a_1 x + a_0$ ，以及一个区间 $[l, r]$ ，保证在范围 $[l,r]$ 内存在一点 $x$ ，使得 $[l,x]$ 上单调增， $[x,r]$ 上单调减。试求出 $x$ 的值。

C++

#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

void solve() {}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n;
  double l, r;
  cin >> n >> l >> r;
  vector<double> nums(n + 1);
  for (int64_t i = n; i >= 0; --i) { cin >> nums[i]; }

  auto f = [&](double x) {
    double res = 0.0;
    for (int64_t i = n; i >= 0; --i) { res += nums[i] * pow(x, i); }
    return res;
  };

  double left = l, right = r;
  while (abs(right - left) > 1e-12) {
    double m1 = left + (right - left) / 3.0;   // 1/3 点
    double m2 = right - (right - left) / 3.0;  // 2/3 点
    if (f(m1) > f(m2)) {                       // 由于右侧单调减，左侧单调增, 极大值在左侧
      right = m2;
    } else {  // 极大值在右侧
      left = m1;
    }
  }
  cout << fixed << setprecision(5) << (left + right) / 2.0 << "\n";
  return 0;
}

Closest Moment

有两条线段，线段 $1$ 的起点为 $(s_{1x}, s_{1y})$ ，终点为 $(g_{1x}, g_{1y})$ ；线段 $2$ 的起点为 $(s_{2x}, s_{2y})$ ，终点为 $(g_{2x}, g_{2y})$ 。两条线段分别以匀速从起点运动到终点，求在运动过程中两条线段之间的最短距离。

Hint

设线段 $1$ 的长度为 $len_1$ ，线段 $2$ 的长度为 $len_2$ ，不妨设 $len_1 \geq len_2$ 。
线段 $1$ 按照线段 $2$ 的长度比例取中点 $mid$ ，则线段 $1$ 可以分为两部分： $(s_1, mid)$ 和 $(mid, g_1)$ 。
分别计算 $(s_1, mid)$ 与线段 $2$ 之间的最短距离，以及线段 $(mid, g_1)$ 与点 $g_2$ 之间的最短距离（此时较短线段已停止移动），二者的较小值即为所求。计算线段与线段之间的最短距离时，可以使用三分法。

计算点与线段之间的最短距离时，可以变换为计算线段与原点之间的最短距离，即将线段的两个端点都减去该点的坐标。

C++

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

using Pdd = pair<double, double>;

Pdd sub(const Pdd &a, const Pdd &b) { return {a.first - b.first, a.second - b.second}; }

double dist(const Pdd &a, const Pdd &b) {
  Pdd d = sub(a, b);
  return sqrt(d.first * d.first + d.second * d.second);
}

Pdd internal_division(const Pdd &a, const Pdd &b,
                      double p) {  // a + (b - a) * p
  return {a.first + (b.first - a.first) * p, a.second + (b.second - a.second) * p};
}

const int NUM_ITERATION = 60;

// 计算线段 AB 与原点最短距离
double dist_segment_and_origin(const Pdd &a, const Pdd &b) {
  auto f   = [&](double t) { return dist(internal_division(a, b, t), {0.0, 0.0}); };
  double l = 0.0, r = 1.0;
  for (int i = 0; i < NUM_ITERATION; ++i) {
    double m1 = (2 * l + r) / 3.0;
    double m2 = (l + 2 * r) / 3.0;
    if (f(m1) < f(m2)) {  // 极小值在左侧
      r = m2;
    } else {  // 极小值在右侧
      l = m1;
    }
  }
  return f((l + r) / 2.0);
}

void solve() {
  vector<Pdd> s(2), g(2);
  cin >> s[0].first >> s[0].second >> g[0].first >> g[0].second;
  cin >> s[1].first >> s[1].second >> g[1].first >> g[1].second;

  // 保证 (s[0], g[0]) 是较长线段
  double len0 = dist(s[0], g[0]);
  double len1 = dist(s[1], g[1]);
  if (len0 < len1) {
    swap(s[0], s[1]);
    swap(g[0], g[1]);
    swap(len0, len1);
  }

  // 长线段按短线段长度比例取中点
  Pdd mid_point = internal_division(s[0], g[0], len1 / len0);

  // 三分法分别计算两段距离
  // (s[0],mid_point) 上的移动点到线段 (s[1],g[1]) 的最小值
  double d1 = dist_segment_and_origin(sub(s[0], s[1]), sub(mid_point, g[1]));
  // (mid_point,g[0]) 上的移动点到最后 (s[1],g[1]) 的最小值
  double d2 = dist_segment_and_origin(sub(mid_point, g[1]), sub(g[0], g[1]));

  cout << fixed << setprecision(15) << min(d1, d2) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while ((t--) != 0) { solve(); }
}

二分查找⚓︎

二分查找⚓︎

三分查找⚓︎

评论