# binary search二分搜
## 模板(偽程式碼)

int solve(int left,int right){
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(條件成立){
            right=mid;
		}
        else{
            left=mid+1;
        }
    }
    return left;//循環結束的條件是left==right,則也可以返回right
}

## 範例練習

zerojudge:d732: 二分搜尋法
https://zerojudge.tw/ShowProblem?problemid=d732

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 2e18
#define maxn 200005
#define mod 1000000007

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,k;
    cin>>n>>k;
    int arr[maxn];
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    while(k--){
        int q;
        cin>>q;
        int left=1,right=n;
        while(left<right){
            int mid=(left+right)/2;
            if(arr[mid]>=q){
                right=mid;
            }
            else{
                left=mid+1;
            }
        }
        if(arr[right]==q){
            cout<<right<<endl;
        }
        else{
            cout<<0<<endl;
        }
    }
}

### codeforces:C. Poisoned Dagger
https://codeforces.com/problemset/problem/1613/C

**題意:**
Monocarp要斬殺一頭巨龍，巨龍的血量為$h$。
Monocarp可以發動$n$次攻擊，每次攻擊於時間$a_i$，持續$k$秒。
每持續 1 秒就會讓巨龍的血量-1。
如果兩個攻擊的間隔小於$k$，後一個攻擊發動時會停止前一個攻擊的效果。
問:斬殺這頭巨龍的$k$的最小值是多少?
**想法:**

**code:**

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 2e18
#define maxn 100005
#define mod 1000000007

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin>>t;
    int arr[maxn];
    while(t--){
        int n,h;
        cin>>n>>h;
        for(int i=1;i<=n;i++){
            cin>>arr[i];
        }
        int left=0;
        int right=1e18;
        while(left<right){
            int middle=(left+right)/2;
            int ans=middle;
            for(int i=1;i<n;i++){
                ans+=min(middle,arr[i+1]-arr[i]);
            }
            if(ans>=h){
                right=middle;
            }
            else{
                left=middle+1;
            }
        }
        cout<<left<<endl;
    }
}