二分手册(持续总结更新)
经过长时间的保守二分法调试的折磨(主要是边界条件的一些细节).
经常看着别人的代码与自己的代码明明是一样的，但是别人的直接AC,我的要么TLE，要么CE，要么SF……..
所以，经过长时间的血泪教训与总结，我开始渐渐摸清楚二分的方法了吧(Maybe?)
对于常用的二分模板来说
最应该考虑二分的目的与意义
二分：翻译成通俗易懂的语言来说，就是找到第一个满足XX条件的数据(前提是在一个有序的数组中)
主要有两种，一种是a[mid] >= target型的，一种是a[mid] <= target型的。
两种不同的表达方式对应着不同的left与right的部署。
while(left < right)
{
int mid = left + right >> 1 ;
if(a[mid] >= target)
{
right = mid ;
}
else
{
left = mid + 1 ;
}
}
//中文就是大于等于target的第一个数字
while(left < right)
{
int mid = left + right + 1>> 1 ;
if(a[mid] > target)
{
right = mid-1 ;
}
else
{
left = mid ;
}
}
//找到的是小于等于target的第一个数字 (只要是right = mid -1 ，要在mid的来源+1)
举一些例子：
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组 {3,4,5,1,2}为 {1,2,3,4,5}的一个旋转，该数组的最小值为 1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为 0，请返回 −1。
样例
输入：nums = [2, 2, 2, 0, 1]
输出：0
这一题是比较经典的利用二分来做的，找最小值的模板题目。
其实如果是比赛做到了，那其实直接sort一下，return nums[0] 好像就可以了……..(好吧，某种程度上说他显然是一道弱智题…….)
但是！！！但是！！！但是！！！
这道题可以锻炼一下我们的二分的熟练度，好吧，现在就用二分来分析一下这道题目，就用刚刚的二分模板。
class Solution {
public:
int findMin(vector& nums) {
int n = nums.size() ;
if(n == 0) return -1 ;
nums.erase(unique(nums.begin() , nums.end()) , nums.end()) ;
n = nums.size() ;
int left = 0 ; int right = n-1 ; //左闭右开
if(nums[right] > nums[0]) return nums[0] ;
while(left < right)
{
int mid = left + right >> 1 ;
if(nums[mid] >= nums[0])
{
left = mid + 1 ;
}
else
{
right = mid ;
}
}
return nums[left] ;
}
};
回顾一下代码：
写二分，重要的一下几点：
一、找到target，即你的对比值是什么。比如这一题他的对比值就是nums[0]。
二、找到你想要的值与target之间的关系，无非就是几种：
第一个小于等于target的数、第一个大于等于target的数，或者是把小于等于什么的改成小于而已…….
三、找对应的模板，背模板的时候注意几点即可。
我个人习惯是一般采用左闭右开的方式，来初始化的left和right。
然后找target与关系，找到之后呢，比如这一题，我要找的是小于nums[0]的第一个数字，那我就考虑left最终应该指向>=nums[0]的最后一个元素的位置再加一。
一般来说，我们最终的破除循环的条件为
while(left < right)
{
...........
}
所以最终状态其实是left == right的，那我们就可以反向进行考虑，最后一步变化的那必然是xxx = mid + 1/mid -1什么的，另外一个值其实再倒数几步的时候是不会变化的，已经锁定住我们要的值了，剩下的其实可以理解为等另外一个变量靠过来，然后破圈即可。所以我们主要考虑的对象其实是xxx = mid ; 的部分。如果是right = mid -1 ;什么的，要注意再确定mid的时候，就需要
mid = left + right + 1>> 1 ;
要不然，血泪教训是
TLE……….死循环……
好的，之后如果有更加经典的例子，我再次会更新。
—————————————-ok 今天是-10-10更新————————————————————————
又发现了一个比较经典的例子
数的范围
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
ok，main函数的部分应该是相当简单了，主要的难点就是在于，如何返回两个值，满足起始与终点的要求。
#include
using namespace std ;
const int N = 100010 ;
int a[N] ;
int n , m ;
int findlow(int *a , int num)
{
int left = 0 ;
int right = n ;
while(left < right)
{
int mid = left + right >> 1 ;
if(a[mid] >= num)
{
right = mid ;
}
else
{
left = mid + 1 ;
}
}
return left ;
}
int findhigh(int *a , int num)
{
int left = 0 ;
int right = n ;
while(left < right)
{
int mid = left + right >> 1 ;
if(a[mid] > num)
{
right = mid ;
}
else
{
left = mid + 1 ;
}
}
return left - 1;
}
int main()
{
cin >> n >> m ;
for(int i = 0 ; i < n ;++i)
{
cin >> a[i] ;
}
for(int i = 0 ; i < m ; ++ i)
{
int b ;
cin >> b ;
int low = findlow(a , b) ;
int high = findhigh(a , b) ;
if(low > high)
low = high = -1 ;
cout << low << " " << high << endl ;
}
return 0 ;
}
运用之前的二分查找法的模板来说，
我们已经知道该题的target，就是目标值了。现在关系也明确了，就是查找>=target的第一个数字和<=target的最后一个数字。
我们知道二分查找模板的宗旨是返回第一个满足的值。那大于等于target的第一个值非常好找，小于等于target的最后一个值应该怎么找呢？
换个思路，那就是找>target的第一个值的位置再减去一咯！！！！！
int findlow(int *a , int num)
{
int left = 0 ; int right = n ;
while(left < right)
{
int mid = left + right >> 1 ;
if(a[mid] >= num)
{
right = mid ;
}
else
{
left = mid + 1 ;
}
}
return left ;
}
int findhigh(int *a , int num)
{
int left = 0 ; int right = n ;
while(left < right)
{
int mid = left + right >> 1 ;
if(a[mid] > num)
{
right = mid ;
}
else
{
left = mid + 1 ;
}
}
return left - 1 ;
}
