二分查找模板

二分查找题目（持续更新）

\(1.\) \(CF835E\)

单调递增序列中查找第一个 \(\leqslant x\) 的数

细节： \(l+r\) 的写法要与 \(mid\) 的写法配套。

$View$ $Code$ int a[MAX]; int leqs(int l,int r,int x) { while(l>1; if(a[mid]>=x) r=mid; else l=mid+1; } return a[l]; }

单调递增序列中查找第一个 \(\geqslant x\) 的数

$View$ $Code$ int a[MAX]; int geqs(int l,int r,int x) { while(l>1; if(a[mid]<=x) l=mid; else r=mid-1; } return a[l]; }

实数域上的二分（可以确定精度，保留 \(k\) 位小数）

细节：左右 \(mid\) 的写法相同。

$View$ $Code$ int k,l=0,r=MAXN; const double eps=1e-(k+2); while(r-l>eps) { double mid=(l+r)/2; if(calc(mid)) r=mid; else l=mid; }

实数域上的二分（不能确定精度）

$View$ $Code$ int tms=MAX,l=0,r=MAXN; for(register int i=1;i<=tms;i++) { double mid=(l+r)/2; if(calc(mid)) r=mid; else l=mid; }

转载于:https://www.cnblogs.com/Peter0701/p/11262810.html