# 二分搜
如果有什麼更好的講法或是好東西想分享的話，可以直接修改。
是說有寫我忘了引用直接放上來。請見諒(我之後會補的)
## 前言
“Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…” — Donald Knuth
1. 什麼是二分搜?
1. 什麼時候需要二分搜?
1. 二分搜什麼情況下有用?
1. 二分搜的特性?
2. 怎麼寫二分搜?
****
如果沒有排序，二分搜起作用嗎?
二分搜的時間複雜度是?(分兩種狀況討論)
**單調性**
這個函數有單調性嗎?
這個呢?
這個呢?
單調列隊(下次說吧?)
****
分治處理
****
**分塊**
順便說一下分塊，之前問的區間最大最小值
直接枚舉是O(N^2)。
區間最大值: https://zerojudge.tw/ShowProblem?problemid=d539
## 簡單介紹c++函數庫
lower_bound(x)嚴格回傳第一個>=x的位置
upper_bound(x)嚴格回傳第一個>x的位置
舉例:x=3，a[5]={3,3,3,4,4};
此時lower_bound(3)?
upper_bound(3)?
## 二分搜的寫法
二分搜最多有64種寫法，他是概念最簡單，但實作超麻煩的一種演算法。~~(當然到後面圖論你們就知道什麼更麻煩了xd)~~
這邊放四種:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[10]={1,1,1,1,2,2,2,3,3};
int val = 2;
int main(){
int n;
cin>>n;
int l=0,r=9;
while(l<=r){
int mid=(l+r)>>1;
if(a[mid]>=val) r=mid-1;
else l=mid+1;
}
cout<<l;
}
```
這裡的程式碼是在找什麼?
如果第14行的l改成r會怎樣?
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[10]={1,1,1,1,2,2,2,3,4,5};
int val =4;
int main(){
int n;
cin>>n;
sort(a,a+9);
int l=0,r=9;
while(l!=r){
int mid=(l+r)>>1;
if(a[mid]>=val) r=mid;
else l=mid+1;
}
cout<<a[l] << ' '<<l;
}
```
我們能不能把l=mid,r=mid-1?為什麼?
這個程式有什麼樣的問題?
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[10]={1,1,1,1,2,2,2,3,5,5};
int val = 3;
int main(){
sort(a,a+9);
int l=0,r=9;
while(l+1<r){
int mid=(l+r)>>1;
if(a[mid]>=val) r=mid;
else l=mid;
}
if(a[l]>=val) cout<<l;
else cout<<r;
}
```
第三種程式碼的二分搜想表達什麼?
easy 二分，跳躍二分搜
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[10]={1,1,1,1,2,2,2,3,5,5};
int main(){
int n = 9 ;
int pos = 0,val=2;
for(int jump=n/2;jump>0;jump/=2){
//cout<<jump<<' '<<pos<<'\n';
while(pos+jump<=n && a[pos+jump]<=val){
pos+=jump;
}
}
cout<<pos+1<<'\n';
}
```
最大的問題:以上的程式碼是在求什麼?
upper_bound? lower_bound? 值? 位置?
## 二分搜的進階運用
它寫成陣列會變成[0,0,0,0,0,0,1,1,1]
問題:這個函數可以二分搜嗎?原因?
problems:
apcs:
基地台: https://zerojudge.tw/ShowProblem?problemid=c575
張貼海報: https://zerojudge.tw/ShowProblem?problemid=h084
圓環出口: https://zerojudge.tw/ShowProblem?problemid=f581
TOI:
裁員風暴: https://zerojudge.tw/ShowProblem?problemid=k185
## 三分搜
如果函數他不具有單調性，而是二次函數，怎麼辦?
:::spoiler 提示
在標題上面
:::
```cpp=
double t_search_y(double x) {
double l = -1000, r = 1000;
for (int i = 0; i < 300; i++) {
double m1 = (2 * l + r) / 3;
double m2 = (l + 2 * r) / 3;
if (f(x, m1) >= f(x, m2)) l = m1;
else r = m2;
}
return f(x, l);
}
double t_search_x() {
double l = -1000, r = 1000;
for (int i = 0; i < 300; i++) {
double m1 = (2 * l + r) / 3;
double m2 = (l + 2 * r) / 3;
if (t_search_y(m1) >= t_search_y(m2)) l = m1;
else r = m2;
}
return t_search_y(l);
}
```
****
### ~~放中二病的男子~~
Sign in with Wallet
Connect another wallet