# 二分搜
## 心得
二分搜算是學習演算法的路上會碰到最基本的幾個演算法之一，而且在往後的比賽之中也會時常見到需要使用二分搜的場合，雖然二分搜的概念並不困難，但在實作上會碰到各式各樣的問題，需要隨著需求不同更改程式碼，有著許多小細節要注意，所以我在此編寫了一個通用模板，可以以相似的想法面對不同類型的題目。
## 二分搜概念
二分搜能運用到的場合相當多，只要是**單調區間**便可使用二分查找，主要的題目類型有:
* 尋找特定值
* 查找第一個大於等於某數的元素
* 查找最後一個小於等於某數的元素
* ...
二分搜說難也難、說簡單也簡單，主要是實作過程中有**許多細節**需要注意:
* left ,right要初始為(0,n-1)還是(0,n)?
* while判斷式中要填left<=right還是left<right?
* 更新left和right時mid要+1還是-1?
就這些細節可知二分搜有許多類型和細節，為求解題方便以下將提出一套思路使你在面對各類型的題目時，都能輕易找出對應的寫法。
---
# 實作
## 大於等於
### 問題定義
給定一**單調上升之數列**，求第一個**大於等於某特定值**的元素索引值並定義其為「下界」，當下界不存在則回傳數組長度。
### 思路
給定數組[1,2,4,5,5,6,7]，令特定值為5則應該回傳下界為3
| 0 | 1 | 2 | ->3 | 4 | 5 | 6 |
| --- | --- | --- |:---:| --- | --- | --- |
| 1 | 2 | 4 | ->5 | 5 | 6 | 7 |
可以看到我們能將數列分為**右側都大於等於特定值**和**左側都小於特定值**，而我們回傳之索引值正好是**大於等於特定值的數列之下界**。
首先，我們以**閉區間**之寫法來表達思路:
* 區間範圍為[left,right]，left指向索引值0，right指向索引值6
* mid為[left,right]的中間位置
* **當left>right時，區間為空**
依據上述思路提出，演算法步驟:
1. 若arr[mid]>=特定值，則[mid,right]區間內所有元素均大於等於特定值，因此right左移，故**right=mid-1**。
2. 否則，則是[left,mid]區間內所有元素均小於特定值，因此left右移，故**left=mid+1**。
3. 重複上述動作直到區間被刪減為空，**此時left將會停在下界，故回傳left**。
### 程式碼
可執行下列程式碼以利思考。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
int n,x;
cin>>n;
for(int i=0;i<n;++i)cin>>a[i];
cin>>x;
sort(a,a+n);
int left=0,right=n-1;//[0~N-1]的閉區間
while(left<=right){//[left~right]大小為零結束
int mid=(right+left)/2;
//cout<<left<<' '<<mid<<' '<<right<<'\n';
if(a[mid]>=x) right=mid-1;
else left=mid+1;
}
cout<<left<<'\n';//回傳索引值
return 0;
}
```
## 小於等於
### 問題定義
給定一**單調上升之數列**，求最後一個**小於等於某特定值**的元素索引值並定義其為「上界」。
### 思路
一樣給定數組 [1,2,4,5,5,6,7]，令特定值為則應該回傳上界為4
| 0 | 1 | 2 | 3 | ->4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 2 | 4 | 5 | ->5 | 6 | 7 |
首先我們一樣能將數列分為右側都大於特定值和左側都小於等於特定值，透過觀察我們可以發現，**小於等於特定值的數列上界和大於特定值下界是相鄰的**所以 **上界 = 下界 - 1**。因此，所有找上界的问题，都可以**轉換為「互補的」找下界的問题**。
* 區間範圍為[left,right]，left指向索引值0，right指向索引值6
* mid為[left,right]的中間位置
* **當left>right時，區間為空**
* 這次要查找的元素為大於特定值，故**right判斷式要改為a[mid]>x**
依據之前的思路提出相同的演算法步驟:
1. 若arr[mid]>=特定值，則[mid,right]區間內所有元素均大於等於特定值，因此right左移，故**right=mid-1**。
2. 否則，則是[left,mid]區間內所有元素均小於特定值，因此left右移，故**left=mid+1**。
3. 重複上述動作直到區間被刪減為空，**此時left將會停在下界而right會停在left-1的位置即為「上界」，故回傳right**。
## 程式碼
可執行下列程式碼以利思考。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
int n,x;
cin>>n;
for(int i=0;i<n;++i)cin>>a[i];
cin>>x;
sort(a,a+n);
int left=0,right=n-1;//[0~N-1]的閉區間
while(left<=right){//[left~right]大小為零結束
int mid=(right+left)/2;
//cout<<left<<' '<<mid<<' '<<right<<'\n';
if(a[mid]>x) right=mid-1;
else left=mid+1;
}
cout<<right<<'\n';//回傳索引值
return 0;
}
```
---
# 總結
二分搜無論是找下界、還是找上界，都可以套用「找下界」的思路來實作：
* 首先是循環條件 若是閉區間的話以left <= right，表示區間不為空，開區間則是以left < right，表示區間不為空。
* 再來if的判定條件和問題的比較規則是相同的，比如要找**满足 x >= target 的第一个元素**，就令 **if a[mid] >= target**；要找**滿足 x > target 的第一个元素**，**就令 if a[m] > target**。
* 接著if為真時，以**閉區間**為例需更新 **right：right = mid - 1**；否則 **left = mid + 1**;而**開區間**則是更新 **right：right = mid** ；否則 **left = mid + 1**。
* 最後當循環结束時，**閉區間**的**left會指向下界**，**right則指向「互補條件」的上界**；而**開區間**的**left和right則都指向下界**
---
# 補充
## 開區間二分搜寫法
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
int n,x;
cin>>n;
for(int i=0;i<n;++i)cin>>a[i];
cin>>x;
int left=0,right=n;//[0~N-1]的開區間
while(left<right){//[left~right)大小為零結束
int mid=(right+left)/2;
//cout<<left<<' '<<mid<<' '<<right<<'\n';
if(a[mid]>=x) right=mid;
else left=mid+1;
}
cout<<left<<'\n';//回傳索引值
return 0;
}
```
## c++二分搜函式
1. **lower_bound( begin,end,num,greater() )**:從陣列的begin位置到end-1位置二分查詢第一個大於或等於num的數字，找到返回該數字的地址，不存在則返回end。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
int n,x;
cin>>n;
for(int i=0;i<n;++i)cin>>a[i];
cin>>x;
cout<<lower_bound(a,a+n,x)-a<<'\n';
//通過返回的地址減去起始地址begin,得到索引值
return 0;
}
```
2. **upper_bound( begin,end,num,greater() )**:從陣列的begin位置到end-1位置二分查詢第一個大於num的數字，找到返回該數字的地址，不存在則返回end。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
int n,x;
cin>>n;
for(int i=0;i<n;++i)cin>>a[i];
cin>>x;
cout<<upper_bound(a,a+n,x)-a<<'\n';
//通過返回的地址減去起始地址begin,得到索引值
return 0;
}
```
3. **binary_search( begin,end,num,greater() )**:從陣列的begin位置到end-1位置二分查詢num是否存在陣列中，找到返回True，不存在則返回False。
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
int n,x;
cin>>n;
for(int i=0;i<n;++i)cin>>a[i];
cin>>x;
if(binary_search(a,a+n, x))
cout << "found" <<'\n';
else
cout << "not found" <<'\n';
return 0;
}
```
{"metaMigratedAt":"2023-06-16T16:48:26.047Z","metaMigratedFrom":"YAML","title":"二分搜","breaks":true,"contributors":"[{\"id\":\"77be2af8-ce15-4578-9f4d-33dde9879cdc\",\"add\":6311,\"del\":1363},{\"id\":\"3978a08d-c47c-4560-b04d-dfbd8e71d0a3\",\"add\":18,\"del\":0}]"}