二分查找

1. 使用前提：有序。
2. 可理解為枚舉的一種技巧。
3. 時間復雜度：$log(n)$

基礎模版代碼

• 使用時根據情景進行相應的變化。
• 注意跳出條件and分支處理方式and返回答案，三者之間的配合，不要進入死循環。
• 可以在模擬一下最后得到答案時的運行情況來判斷。

int bs(int a[],int n,int tg)
{int l=0,r=n-1;while(l<=r){int mid=(l+r)/2;if(a[mid]==tg) return mid;else if(a[mid]>tg) r=mid-1;else l=mid+1;}return -1;
}

常見題型

求最值

• 洛谷1873 砍樹
• 力扣073 愛吃香蕉的狒狒

最小化最大值

1. 有多個分段，通過移除操作，得到一個最小的分段最大值。

• 洛谷2678 跳石頭

最大化最小值

1. 有多個分段，通過移除操作，得到一個最大的分段最小值。