二分

参考资料

二分（Binary Search）利用答案的单调性，每次将区间折半，时间复杂度为 $O(\log n)$ 。

check 函数的返回值应为 $\set{0,0,\dots,0,0,1,1,\dots,1,1}$ 。

二分结束后， $l$ 为第一个 $1$ 的位置， $l-1$ 为最后一个 $0$ 的位置。

83 Bcpp
int l=x,r=y+1;
while(l<r)
{
	int mid=l+r>>1;
	if(check(mid))r=mid;
	else l=mid+1;
}

90 Bcpp
double l=x,r=y;
while(r-l>eps)
{
	double mid=(l+r)/2;
	if(check(mid))r=mid;
	else l=mid;
}

三分（Ternary Search）用于求单峰（单谷）函数的极值点。每次在区间内取三等分点 $m_1,m_2$ ，比较 $f(m_1)$ 与 $f(m_2)$ 的大小来排除不含极值的一侧，时间复杂度为 $O(\log n)$ 。

找最大值时若 $f(m_1)>f(m_2)$ ，排除右侧；找最小值时若 $f(m_1)<f(m_2)$ ，排除右侧。

103 Bcpp
double l=x,r=y;
while(r-l>eps)
{
	double m1=(l*2+r)/3,m2=(l+r*2)/3;
	if(f(m1)>f(m2))r=m2;
	else l=m1;
}

输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots,a_n$ ，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$ ，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$ 。

给定 $n$ 个形如 $ax^2+bx+c$ 的二次函数 $f_1(x),f_2(x),\dots,f_n(x)$ ，设 $F(x)=\max f_i(x)$ ，求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

给出一个 $N$ 次函数，保证在范围 $[l, r]$ 内存在一点 $x$ ，使得 $[l, x]$ 上单调增， $[x, r]$ 上单调减。试求出 $x$ 的值。

有两个城市，中间相隔着一条笔直的河，现在要修路修桥将这两个城市联通，请找出一种方案使总的花费最小。