一、整數二分演算法
1.1 撰寫整數二分，記住下面的內容，代碼也就游刃有余了！
(1) 首先找到陣列的中間值，mid=(left+right)>>1，區間[left, right]被劃分成[left, mid]和[mid + 1, right]；如果是mid = l + r + 1 >> 1，區間[left, right]被劃分成[left, mid - 1]和[mid, right]，
(2) 然后通過check(mid)判斷中間值是不是滿足這個性質,check是根據不同的題型撰寫的，
(3) 最后就能使用折半，縮小區間了，如果區間縮到了1，那么那個也就是答案，
二、整數二分演算法的核心
2.1 二分的本質不是單調性
(1) 如果有單調性，一定可以二分，但是可以二分的題目，不一定有單調性，
(2) 二分的本質，問題一半滿足，一半不滿足，可以尋找到邊界，這個邊界可以將陣列分為兩個部分，因為整數邊界必須做出選擇，代碼將有兩個模板，而浮點數不是，
2.2 二分的主要思想是折半
二分一定是有解的，那個邊界可以二分出來，但題目可能是無解的，
三、整數二分演算法的代碼模板
bool check(int x) {/* ... */} //檢查x是否滿足某種性質
// 區間[left, right]被劃分成[left, mid]和[mid + 1, right]時使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;//左邊，check()判斷mid是否滿足性質
else l = mid + 1;//右邊
}
return l;
}
// 區間[left, right]被劃分成[left, mid - 1]和[mid, right]時使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) r = mid-1;//左邊
else l = mid;//右邊
}
return l;
}
查看更多
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91964.html
標籤：其他
上一篇：二維陣列中的查找
下一篇：求教雙向dijkstra大佬們