二分查找

【二分查找】（O(logn)）

1.什么是二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法

2.条件

首先需要明确的是二分查找的对象应满足单调性，此外在查找过程中需时刻注意边界（卡死循环就寄了）

具体代码如下

int l=1,r=n;//设立边界 
while(l<=r){
    int mid=l+r>>1;//取中间值 
    if(check(mid)) l=mid+1;//满足条件时意味着另一边的也符合要求所以要移动边界找到the best one 
    else r=mid-1;//同上 
}

【二分答案】

1.什么是二分答案

二份答案即使用二分查找在一个满足单调性的区间[l,r]中查找一个最符合要求的答案

关键词：最大XX最小值，最小XX最大值

2.什么是check（上代码所提及的函数）

check函数，顾名思义，就是对于当前查找的答案mid进行验证，验证其是否符合题目要求，进而对当前区间做出修改

而对于check的编写，因为我很菜，做的题也不多，但到现目前我做的二分答案的所用的check都是将查找到的答案进行模拟，然后在模拟过程中根据题目的要求返回true or false

3.如何找到题目中可以被二分的对象

（1）如果给出的序列满足单调性　　如果题目的答案是序列中的某数，那么可以试着对序列进行二分查找（l=1,r=n）

（2）如果给出的序列不满足单调性　如果题目的答案为方案数或者最...（例如砍树、奥特曼打怪、建别墅+），那么可以试着对于方案数或者最...的极大值进行二分查找（区间不定，视题目而设）

（3）没有明显给出的单调性　　　　如果题目看起来不可能用二分，那么可以试着用代数式表示一些变量间的关系，根据关系式作出函数图像，截取图像中具有单调性且正确的一段进行二分