<style type="text/css"> .slides { text-align: left !important; } </style> # 二分搜尋 Author: PixelCat --- ## 問題敘述 給你一個只有01的序列，0只會出現在1前面 序列長度是 $N$，第 $i$ 格是 $f(i)$ ---- 像是  或者  甚至  ---- 我們不知道這個序列長怎樣 但我們可以多次選一個位置 $i$ 詢問：「$f(i)$ 是1嗎?」 我們希望用最少的詢問找出第一個1的位置 --- ## 暴力出奇蹟 ---- 從第一格開始往後問 哪天終於問出1就找到答案了 簡單，直覺，有效 ---- 最差情況下假如最後一格才出現1 總共要詢問 $N$ 次 ---- 這種辦法小學生都會 還可以更好嗎? 不行的話我就不會寫這份投影片了 --- ## 改進 ---- 為了改進我們需要一點觀察與偷懶 > 0只會出現在1前面 剛剛好像沒用到這個性質 有他就可以偷懶了 ---- 你今天什麼都還不知道 丟兩顆骰子決定詢問這一格  ---- 假如你發現他是1  後面還會出現0嗎? 不可能  那他們自然不會是答案，可以不理他了  ---- 假如你發現他是0  前面還會出現1嗎? 不可能  那他們自然不會是答案，可以不理他了  ---- ### 二分搜! 假如我們確定答案在 $[L,R]$ 區間裡面 找到正中間 $m=\left \lfloor{\frac{L+R}{2}}\right \rfloor$，詢問 $f(m)$ - 假如 $f(m)=1$，答案一定在 $[L,m]$ 裡面 - 假如 $f(m)=0$，答案一定在 $[m+1,R]$ 裡面 一直到最後 $L=R$，答案就是他了 ---- 為何正中間? 假如選正中間，一定可以刪掉一半 假如不選正中間，可能刪掉不到一半 ---- 總共要問幾次? 一開始「答案區間」的長度 $R-L+1=N$ 每問一次，答案區間變短一半 最後 $R-L+1=1$ $$ N\times\left(\frac{1}{2}\right)^x=1\\ x=\log_2N $$ 就算 $N=1024$，問個10次就完事了 ---- ### 示意code ```cpp= int lo = 1, hi = N; while(lo != hi){ int m = (hi + lo) / 2; if(f(m) == 1) hi = m; else lo = m + 1; } cout << lo << "\n"; ``` --- ## 一定要是序列嗎 ---- 給你一個函數，吃一個實數，吐0或1回來 0依然不會出現在1後面 $$ f:\mathbb{R}\rightarrow \left\{0,1\right\}\\ x_1\leq x_2\Longrightarrow f(x_1)\leq f(x_2) $$ 請問分界點在哪裡? 一開始確定答案在 $[0,C]$ 裡 輸出跟正確答案的差異在 $\epsilon=10^{-9}$ 以內都算正確 ---- 跟剛剛相同的想法 假如某個地方是$1$，那後面全部都會是$1$ 假如某個地方是$0$，那前面全部都會是$0$ 還是可以偷懶! ---- 假如現在答案可能出現在 $[L,R]$ 之間，那就戳 $m=\frac{L+R}{2}$ 假如$f(m)=1$，那答案一定在$[L,m]$裡 假如$f(m)=0$，那答案一定在$[m,R]$裡 ---- ### 複雜度 每次切一半，一開始$R-L=C$，切到 $R-L\leq \epsilon$ 為止 $$ C\times(\frac{1}{2})^x\leq \epsilon \\ x\geq\log{\frac{C}{\epsilon}} $$ 複雜度$\mathcal{O}(\log{\frac{C}{\epsilon}})$ ---- ### 實作 ```cpp= double lo = 0, hi = C; double eps = 1e-9; while(hi - lo > eps){ double m = (hi + lo) / 2; if(f(m)) hi = m; else lo = m; } cout << lo << "\n"; ``` ---- ### 蛤? 可是  ---- 精度爆了 怎麼辦? 改判斷條件 ---- 搜幾輪取決於題目給的範圍和時限 ~~二分搜搜幾輪才會TLE~~ ```cpp= double lo = 0, hi = C; for(int R = 0;R < 100;R++){ //搜100輪 double m = (hi + lo) / 2; if(f(m)) hi = m; else lo = m; } cout << lo << "\n"; ``` --- ### 那... 大多數問題都不會直接給你這個序列(函數)怎麼辦? ---- ### 所以 很多問題要你求一個最大(小)的答案滿足某個條件 而且 1. 直接做不好做 2. 給一個可能的答案可以很方便的驗證行不行 3. 有單調性 搜他! --- ## 經典到發臭的經典題 [zerojudge c575 基地台](https://zerojudge.tw/ShowProblem?problemid=c575) 某數線上有 $N$ 個服務點，座標在 $x_1, x_2, \dots x_N$，你可以任選位置蓋 $K$ 個基地台來服務這些服務點，每個基地台分別可以覆蓋距離他們 $R$ 以內的所有服務點。 請問：$2R$ 最小可以是多少？ $1\leq K<N\leq 5\times 10^4$ $\left|x_i\right|\leq 10^9$ ----  $K=1$ ，最小的 $2R$ 是7，基地台在 $x'_1=4.5$ 處 $K=2$ ，最小的 $2R$ 是3，基地台在 $x'_1=2,\,x'_2=6.5$ 處 $K=3$ ，最小的 $2R$ 是1 ---- 直接做要怎麼做? 我不會 ;w; ---- 給一個答案(半徑)可以驗證嗎? 從左邊掃到右邊，滿足每個服務點都被蓋到的同時盡可能把基地台設在越右邊越好，不虧 可以 $\mathcal{O}(N)$ 驗證! ---- 滿足二分搜條件嗎? 假如這個半徑可以，那半徑變大一定也可以 假如這個半徑不行，那半徑變小一定更不行 條件滿足了 ---- 搜他 $\mathcal{O}(N\log{10^9})$ --- ## C++內建二分搜 ---- 假如是要在排序好的陣列中找一個值 有內建的函數可以做到 複雜度是 $\mathcal{O}(\log($陣列長度$))$ ---- ```cpp= vector<int>v{3,5,6,7}; x=3; p=lower_bound(v.begin(),v.end(),x)-v.begin(); cout<<p<<'\n';// 0 p=upper_bound(v.begin(),v.end(),x)-v.begin(); cout<<p<<'\n';// 1 ``` --- ## 例題 codeforces->problemset->binarysearch [CSES-Array Division](https://cses.fi/problemset/task/1085) [CSES-Factory Machines](https://cses.fi/problemset/task/1620) [CSES-Multiplication Table](https://cses.fi/problemset/task/2422) --- ## 以上 ---- 二分搜概念簡單 但稍作修改包裝就可以變出各種妖魔鬼怪 許多進階的主題也都會用到 例如：線段樹、LCA等 ~~真是陰魂不散~~ ---- 所以要學好二分搜喔~