<style> .reveal .slides { text-align: left; } p, h1, h2, h3, h4, h5, h6 { font-weight: 200px !important; font-family: arial-next !important; } </style> # 二分搜 --- 前綴和複習 ---- 前綴和在幹嘛? ---- 今天我想要更改一個數字 時間複雜度? ---- 更改一個數字 更新prefix_sum: $O(n)$ 查詢: $O(1)$ ---- 來點猛的，我可以做到 更新: $O(logn)$ 查詢: $O(logn)$ ---- 怎麼做？ ###### BIT [友情連結: 台南一中資訊社TFcis](https://youtu.be/jYp9NV2Qi-8?t=372) --- 搜尋一個數列，數字位置？ ---- [4, 6, 8, 3, 9, 2] 4在哪？ 你的方法時間複雜度是多少？ ---- $O(n)$ ```cpp for (int i = 0; i < n; i++) { if (array[i] == x) { // x found at index i } } ``` ---- 有沒有辦法更快？ ---- 如果數列有序？ ---- 終極密碼！！ 最少要猜幾次？ 最多要猜幾次？ 怎麼猜最快 --- 二分搜 ---- $O(logn)$ ``` cpp #include <bits/stdc++.h> using namespace std; int binary_search(vector<int> &v, int k) { int l = 0, r = v.size() - 1; while (l < r) { int mid = (l + r) / 2; if (v[mid] < k) l = mid + 1; else r = mid; } return l; } int main() { vector<int> v = {1, 3, 4, 6, 7, 9, 10}; cout << binary_search(v, 6) << endl; } ``` ---- 找最左邊的1? ``` cpp #include <bits/stdc++.h> using namespace std; int binary_search(vector<int> &v, int k) { int l = 0, r = v.size() - 1; while (l < r) { int mid = (l + r) / 2; if (v[mid] < k) l = mid + 1; else r = mid; } return l; } int main() { vector<int> v = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1}; cout << binary_search(v, 1) << endl; } ``` ---- ###### 應用：找最小可行解 ex: NCPC2020 L ###### 給你$n \times m(1<= n, m <= 1000)$的格子 ###### David要從左上走到右下，只能往下或往右 ###### 每經過一個格子David可能加血或扣血，不能讓David死掉(Hp <= 0) ###### 請問David的初始生命值至少要多少？  ---- 每次走最大的 (X) 如果一開始知道他的生命值，就可以知道他能不能成功從左上走到右下！ ---- 解答：二分搜 --- 三分搜? ---- 找$5x^2+4.76x+666$的極值 ---- ###### [友情連結: 資訊之芽算法班2018 第四週Enumeration_inclass](https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/enumeration_inclass.pdf) ---- 一些例子 NCPC2020 M... --- 我們這兩週學會了什麼？ ---- 前綴和 + 二分搜？？ ---- 前綴和 + 二分搜? 可以找第k大的數字 ---- 怎麼做？ ``` cpp vector<int> v = {2, 4, 3, 9, 5, 8, 1, 2, 5}; int a[100005]{}; // 陣列a存每個數字的出現次數 for(int t : v) a[t]++; // a[] = {0, 1, 2, 1, 1, 2, 0, 0, 1} // prefix_sum = {0, 1, 3, 4, 5, 7, 7, 7, 8} ``` ---- 分析複雜度 建好a陣列和前綴和 $O(n)$ 搜尋第k個位置$O(logn)$ ---- 好像沒有比較厲害... ---- 加修改！用前面提到的BIT 修改$O(logn)$ 查詢$O(logn)$ ---- 找區間第k大? 持久化線段數