二分搜索&二分答案

前言:

​ 大家可以发现，越接近需要查询的单词，翻动书面的页数就越少。你肯定不会从第一页开始一面一面翻，逐个查看每个单词是否就是自己想要查的单词，这样做就太慢了。虽然实际情况不是那么精确，但是基本上使用了“二分思想”。

​ 如果序列是有序的，就可以通过二分查找快速定位所需要的数据。除此之外，二分思想还能求出可行解的最值问题，比如想知道某款手机最高能多少楼高度摔下来而不会摔坏，使用二分的方式可以用最小实验次数就能得到结果（当然你需要准备好几个样品）。

tips:

• 复杂度：floor(log2n)；
• 二分答案应该是在一个单调闭区间上进行的。也就是说，二分答案最后得到的答案应该是一个确定值，而不是像搜索那样会出现多解。二分一般用来解决最优解问题。
• 如果题目规定了有“最大值最小”或者“最小值最大”的东西，那么这个东西应该就满足二分答案的有界性和单调性。
• 而且！和普通解题思路不一样。一般是由题按图索骥找答案，这个二分意思是去*“二分答案”*，用答案碰撞！

知识支撑：

• 快读

  StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  		st.nextToken();
  		int n = (int) st.nval;
  

• 贪心

答题框架：

• while循环
• 循环内判断左缩还是右缩的条件
• 左右中三点进行二分

			while(【l<r】){	//*1	
				int mid = l+(r-l)/2；
				if(【】){
					r=【】;//*2
				}else{
					l = mid+1;//*3	
				}
			}
			if(【judge】){
				System.out.print();
			}else{
				System.out.print();
			}

坑点：

• 有三个符号贼难搞定：上述代码框架里的123····

• • 也就是边界问题：https://www.luogu.com.cn/blog/HOJQVFNA/qian-tan-er-fen-di-bian-jie-wen-ti这个不错

​ 人家的例子的确不错！ 上模板：

/*
* 记录答案法
*/
while (l<=r)
{
    int mid=(l+r)/2;
    if (check(mid))
    {
        ans=mid;
        r=mid-1;
    }
    else l=mid+1;
}
printf("%d",ans);

/*
* 不记录答案法
*/
while (l<r)
{
    int mid=(l+r)/2;
    if (check(mid)) r=mid
    else l=mid+1;
}
printf("%d",l); //r也可以

我做的例题：

https://www.luogu.com.cn/training/111#problems