# 二分搜
#### 中一中電研算法班第三堂社課
---
## 這我
* 蔣承叡
* wifecake
* 111資訊能競
* 112資訊能競
* 管樂社打擊
* APCS之恥
---
# slido
---
## 大綱
* 二分搜
* 跳躍式二分搜
* 對答二分搜
* 三分搜
---
## 二分搜
----
### 先備知識
* 陣列
* 迴圈
* 時間複雜度
* 空間複雜度
----
給你一個長度為 $n$ 的陣列 $a$ ， $q$ 次詢問，
第 $i$ 次詢問給一個數字 $x_i$ ，
求 $x_i$ 有沒有在 $a$ 中出現
$(n\leq 10^5,\ q\leq 10,\ 1\leq x_i,a_i\leq 10^5)$
----
#### 水題la
只要每次詢問都跑一遍 $a$ 看有沒有就好了
```cpp=
void solver(int n,int q,vector<int> a)
{
for(int i=0;i<q;++i) // 跑q次
{
int x; cin>>x;
for(int j=0;j<n;++j) // 最多跑n次
if(a[j]==x)
{
// 在陣列a裡面找到x了
break; // 跳出遍歷a的迴圈
}
}
}
```
時間複雜度為 $O(n*q)$
空間複雜度為 $O(n)$
----
那如果 $(n\leq 10^5,\ q\leq 10^5,\ 1\leq x_i,a_i\leq 10^5)$ 呢?
----
發現可以對質域開一個布林陣列 $g$ ，
$g_i$ 表示元素 $i$ 有沒有在陣列 $a$ 中
----
#### 範例程式
```cpp=
const int N=1e5+5; // 1 <= a_i,x <= 10^5
void solver(int n,int q,vector<int> a)
{
vector<bool> g(N);
for(int i=0;i<n;++i) // 跑n次
g[a[i]]=true;
for(int i=0;i<q;++i) // 跑q次
{
int x;
cin>>x;
if(g[x])
{
// 陣列a裡面有x
}
else
{
// 陣列a裡面沒有x
}
}
}
```
時間複雜度為 $O(n+q)$
空間複雜度為 $O(N+n)$
----
那那那如果
$(n\leq 10^5,\ q\leq 10^5,\ 1\leq x_i,a_i\leq 10^{18} )$
要怎麼辦?
----
## 用二分搜!
如果有一個好方法，能很快的在陣列 $a$ 裡面找到最小的數 $a_k$ 滿足 $a_k\ge x$ 的話
就只要檢查 $x$ 跟 $a_k$ 是否相等就能知道 $a$ 裡面有沒有 $x$ 了
----
### 二分搜的條件
1. 單調性
1. 可在時限內對答
----
先把陣列 $a$ 由小到大排序，
發現可以用 "大於等於 $x$ " 來把陣列 $a$ 分成前後兩個部分，
前面部分的所有數值皆小於 $x$ ( $a_i\ge x$ 為 False )，
後面部分的所有數值皆大於等於 $x$ ( $a_i\ge x$ 為 True )
**所以當用 "是否小於 $x$ " 來區分排序過的陣列 $a$ 時，就滿足了單調性**
----
當陣列 $a$ 如下，且 $x=24$ 時的單調性示意圖
而右邊區間的第一個數字即為大於等於 $x$ 的最小值，為25
----
**而要驗證一個數 "是否小於 $x$ " 只需要 $O(1)$，
因此滿足可在時限內對答的條件。**
時限依據測資大小與整體程式的時間複雜度變動
----
滿足條件後，
發現只要每次檢查陣列 $a$ 正中間的數 $(a_k,\ k=\lfloor \cfrac{n}{2} \rfloor)$ 是屬於左邊區間還是右邊區間。
若 $a_k$ 屬於左邊區間，則 $[1,k]$ 皆不可能為所求的右邊區間第一個數。
若 $a_k$ 屬於右邊區間，則 $[k+1,n]$ 皆不可能為所求的右邊區間第一個數。
把不可能的答案從區間刪掉，重複做直到找到分界點
----
一直更新 $a$ 的話太花時間了，因此改成維護一個 $a$ 的區間 $[l,r]$ 代表目前的剩餘元素
----
#### 範例程式
```cpp=
// 1 <= a_i,x <= 10^18, 需要用long long 存
using ll=long long;
void binary_search(int n,int q,vector<ll> a)
{
sort(a.begin(),a.end());
// lambda
auto check=[&](int m,int x){ // 對答
// return 0 -> 右邊區間
// return 1 -> 左邊區間
return a[m]<x;
};
for(int i=0;i<q;++i)
{
int x;
cin>>x;
int l=0,r=n-1;
while(l<=r) // 最多lg(n)次
{
int m=l+r>>1; // 中點
if(check(m,x)) // v[m]屬於左邊區間
l=m+1;
else // v[m]屬於右邊區間
r=m-1;
}
// a[l]為右區間的第一個數
if(l==n or a[l]!=x) // 右區間為空 or a[l]!=x
{
// a中沒有x
}
else // 右區間非空且右區間的第一個數a[l]等於x
{
// 在a中找到x了
}
}
}
```
[Zerojudge d732](https://zerojudge.tw/ShowProblem?problemid=d732)
----
#### 複雜度分析
每跑一次while迴圈就會把區間減半，
所以對於一個查詢while迴圈最多跑 $\log_2 n$ 次
while迴圈跑一次需要的時間複雜度即為check function的時間複雜度，在這題是O(1)，
因此時間複雜度為 $O(q\log n)$
僅開了一個陣列 $a$ ，空間複雜度為 $O(n)$
----
### lower_bound
### upper_bound
----
```cpp=
using ll=long long;
void binary_search(int n,int q,vector<ll> a)
{
sort(a.begin(),a.end());
for(int i=0;i<q;++i)
{
int x;
cin>>x;
auto it=lower_bound(ALL(v),x);
if(it==v.end() or *it!=x)
cout<<"0\n";
else
cout<<it-v.begin()+1<<'\n';
}
}
```
----
### 題單
[Zerojudge f993](https://zerojudge.tw/ShowProblem?problemid=f993)
[Zerojudge k520](https://zerojudge.tw/ShowProblem?problemid=k520)
---
## 跳躍式二分搜
----
從原本的維護 $[l,r]$ 改成只維護一個 $k$ 紀錄左右區間的分界點，
不斷嘗試把 $k$ 增加。
----
```cpp=
using ll=long long;
void binary_jump_search(int n,int q,vector<ll> a)
{
sort(a.begin(),a.end());
auto check=[&](int m,int k){
return a[m]<k;
};
for(int i=0;i<q;++i)
{
int x;
cin>>x;
int k=-1;
// 跳躍式二分搜
for(int jp=n;jp;jp>>=1)
while(k+jp<n and check(k+jp,x))
k+=jp;
if(k==n-1 or a[k+1]!=x) // 全部的數都小於x or 第一個大於x的數跟x不相等
{
// a沒有x
}
else
{
// a裡面有x
}
}
}
```
---
## 對答二分搜
----
#### [Zerojudge f815](https://zerojudge.tw/ShowProblem?problemid=f815)
給定n個士兵和他們的初始等級，
每人升x等需x^2枚金幣，
現有c枚金幣，問全體最少可到幾等?
(n<=2e4, c<=1e14, level_i<=1e7)
----
二分搜，但是搜誰?
----
#### 對等級二分搜!
----
範例程式
```cpp=
using ll=long long;
const ll N=1e7+5;
// 回傳c塊錢最多可以讓n個士兵升到多少等級
// level 為每個士兵的初始等級
ll solver(int n,ll c,vector<ll> level)
{
ll ans=-1;
// lambda
auto check=[&](ll k){ // 回傳c塊錢是否夠把所有士兵升到k等
ll cost=0;
for(int i=0;i<n;++i) // 跑n次
if(level[i]<k)
cost+=(k-level[i])*(k-level[i]);
return cost<=c;
};
// 跳躍式二分搜
for(ll jp=N;jp;jp>>=1)
while(ans+jp<=N and check(ans+jp))
ans+=jp;
return ans;
}
```
----
#### 複雜度分析
對於一個等級 $k$ ，要驗證是否能夠把所有士兵升到k等的check function要花 $O(n)$ 時間。
因此我們直接對等級二分搜的時間複雜度會是 $O(n\lg (n))$
----
### 關鍵字：最大值最小化/最小值最大化
**有這個基本上可以秒猜對答二分搜**
**可檢查性質**
答案在一個固定區間，並符合單調
| 1 | 2 | 3 | 4 |5 | 6 | 7 | 8 | 9 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| False | False |False | False | True | True | True | True | True |
| 0 | 0 |0 | 0 | 1 | 1 | 1 | 1 | 1 |
----
[APCS:2022/10/4 第四題](https://zerojudge.tw/ShowProblem?problemid=j125)
----
#### 複雜度分析
---
## 三分搜
----
#### [Zerojudge f990](https://zerojudge.tw/ShowProblem?problemid=f990)
在二維坐標系上給 $n$ 個點和一條線 $y=ax+b$ ，
求在線上取一點到 $n$ 個點的距離總和最短
----
沒有單調性?!
----
### 發現性質
假設答案為 $y=ax+b$ 線上的點 $P(x_0,y_0)$ ，
同在線上越趨近於 $(x_0,y_0)$ 的點，距離 $n$ 個點的距離總和越短。
----
也就是說，把原本的 $x$ 軸沿用，距離 $n$ 個點的距離總和當作 $y$ 軸，會得出一個凹口向上的平滑函數
{"title":"二分搜講義","description":"binary search\nbinary jump search\nbinary search on answer\nternary search","contributors":"[{\"id\":\"d807e7fd-fc10-4c0f-bb04-11b9dd1c8f26\",\"add\":9259,\"del\":3471},{\"id\":\"cd1afb5c-6882-4e01-b60e-ca5756cb694b\",\"add\":5799,\"del\":5627}]"}