--- ###### tags: `2020 師大附中校隊培訓` --- # 二分搜與三分搜 ## 2020 師大附中校隊培訓 #### joylintp #### 10.27.2020 --- ## 猜數字 有一整數$n\ (1 \leq n \leq 10^6)$， 每次你可以猜一個介於$1$和$10^6$間的整數， 若$n$大於或等於你猜的數字，你會收到 `>=` 否則，你會收到 `<` 你必須在$25$次內猜到答案 ([Gym - 101021 1](https://codeforces.com/gym/101021/problem/1)) ---- 逐個數字猜 → 至多需要猜$10^6$個數字 → Wrong Answer ---- 每次從已知的可能範圍切一半猜 → 至多需要猜$\lceil log_2(10^6)\rceil = 20$次 → Accepted ---- ```cpp= #include<bits/stdc++.h> using namespace std; signed main() { int l = 0, r = 1000001; string res; while (l != r) { int m = (l + r) / 2; cout << m << '\n', fflush(stdout); cin >> res; if (res == ">=") l = m + 1; else r = m; } cout << "! " << l - 1 << '\n'; return 0; } ``` --- ## 二分搜陣列內容 有一長度為$n\ (1 \leq n \leq 10^5)$的遞增陣列， 找出$x$在陣列中的位置，或$x$不存在於陣列中 ---- 一項一項找 → $O(n)$ ---- 設陣列中間那項的值為$k$ 若$k>x$，則$x$只可能在陣列的左半邊 若$k<x$，則$x$只可能在陣列的右半邊 若$k=x$，則找到答案 → $O(log(n))$ ---- ```cpp= #include<bits/stdc++.h> using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, x, t; vector<int> v; cin >> n >> x; for (int i = 0; i < n; i++) cin >> t, v.push_back(t); int l = -1, r = n, ans = -1; while (l != r) { int m = (l + r) / 2; if (v[m] == x) { ans = m; break; } else if (v[m] < x) l = m + 1; else r = m; } if (ans != -1) cout << ans << '\n'; else cout << "QQ" << '\n'; return 0; } ``` ---- ### lower_bound ```cpp= vector<int> v = {1, 2, 3, 5, 6}; cout << lower_bound(v.begin(), v.end(), 2) - v.begin() << '\n'; // -> 1 cout << lower_bound(v.begin(), v.end(), 0) - v.begin() << '\n'; // -> 0 cout << lower_bound(v.begin(), v.end(), 4) - v.begin() << '\n'; // -> 3 cout << lower_bound(v.begin(), v.end(), 7) - v.begin() << '\n'; // -> 5 // lower_bound回傳第一個「大於或等於」x的元素的iterator ``` ---- ```cpp= #include<bits/stdc++.h> using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, x, t; vector<int> v; cin >> n >> x; for (int i = 0; i < n; i++) cin >> t, v.push_back(t); int pos = lower_bound(v.begin(), v.end(), x) - v.begin(); if (pos >= v.size() || v[pos] == x) cout << pos << '\n'; else cout << "QQ" << '\n'; return 0; } ``` ---- ### upper_bound ```cpp= vector<int> v = {1, 2, 3, 5, 6}; cout << upper_bound(v.begin(), v.end(), 2) - v.begin() << '\n'; // -> 2 cout << upper_bound(v.begin(), v.end(), 0) - v.begin() << '\n'; // -> 0 cout << upper_bound(v.begin(), v.end(), 4) - v.begin() << '\n'; // -> 3 cout << upper_bound(v.begin(), v.end(), 7) - v.begin() << '\n'; // -> 5 // upper_bound回傳第一個「大於」x的元素的iterator ``` --- ## Water Lily (CF 1199B)  ---- 簡化題目：  給$H=\overline{BC}$，$L=\overline{CD}$， 已知$\overline{AB}=\overline{AD}$，求$\overline{AC}$長度 答案誤差需小於$10^{-6}$ ---- $\overline{AC}^2 + L^2 = \overline{AD}^2$ $=(\overline{AC} + H)^2$ → 對$\overline{AC}$長度進行二分搜 ---- ```cpp= #include<bits/stdc++.h> using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); double h, l; cin >> h >> l; double a = 0, b = 1e12; // AC線段長度左右界 while (abs(a - b) > 1e-7) { double m = (a + b) / 2; if (pow(m, 2) + pow(l, 2) < pow(m + h, 2)) b = m; else a = m; } cout << fixed << setprecision(16) << a << '\n'; // 輸出至小數後16位減少誤差 return 0; } ``` ----  對一具有單調性的函數，我們可以進行二分搜 二分搜時詢問左右界間的正中間位置 並根據詢問結果決定將 左界向右移或右界向左移至中間位置 --- ## 尋找二次函數極值 ---- 尋找二次函數的極值時， 我們則將左右界之間平分成三等份， 並對此函數進行三分搜 ----  設四直線由左到右為$x=l, x=m_1, x=m_2, x=r$， 我們能藉由$f(l), f(m_1),f(m_2), f(r)$的大小關係判斷函數頂點的位置 ---- 若 1. $f(l) < f(m_1) < f(m_2) < f(r)$ 或 2. $f(l) > f(m_1) < f(m_2) < f(r)$ 則函數的極值不會在$x=m_2, x=r$兩直線間 ----- 若 1. $f(l) > f(m_1) > f(m_2) < f(r)$ 或 2. $f(l) > f(m_1) > f(m_2) > f(r)$ 則函數的極值不會在$x=l, x=m_1$兩直線間