二分和离散化

为什么把二分和离散化放一起：因为离散化其实是一种二分整数的过程。

二分

相信大家都接触过二分查找（折半查找），这就是二分的思想。

二分通过每次舍弃一半并不存在答案的区间，进而快速锁定要求的答案（二分一定有解，但解不一定就是答案，后面会说）

二分模板：

bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;    // check()判断mid是否满足性质else l = mid + 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}

说一下版子二为什么要+1：因为涉及到mid - 1，+1是为了防止数组越界的，l < r ，所以r > 0，所以(  + r + 1 >> 1) > = 1，因而r更新的时候一定大于等于0，这也就防止了越界。

当然这只是针对于整数二分的边界问题，浮点数二分就不用考虑这个多了，直接除2就可以。

例题：

1、AcWing 789. 数的范围 - AcWing

2、AcWing 790. 数的三次方根 - AcWing

题一：直接套用两个模板，二分出左右区间。判断-1的方法：首次二分出来的区间的下标对应的数组元素并不等于给定要查找的那个数。

题二：不要的左右边界设置成-n 和 n，这样无法处理小数的情况，因为他们的三次方根都会落在-n到n范围的外面，但它也会有解。这也解释了为什么二分一定有解，但是解不一定是答案（解不对）

离散化

先来看一下百科的离散化的定义：

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：

原数据：1,999,100000,15；处理后：1,3,4,2；

原数据：{100,200}，{20,50000}，{1,400}；

处理后：{3,4}，{2,6}，{1,5}；

离散化，就是把一些分布很稀疏的数重新按着他的序号排序，比如我们现在有数据10^9、 1、 5000、 100000 这组数离散化之后的结果就是4、 1、 2、 3 可以看到结果其实就是他们的次序大小。

一般的我们先把这组数据排序然后在离散化，这样得到的结果就是1、2、3、4、5、6.... n.一组连续的整数，这样就可以存到数组里面然后随机访问。

当题目中给的数据范围很大，比如是-10^9到10^9，但是数据规模很小，如n = 10^5。这时候首当其中的就要考虑离散化。因为，我们无法创建一个合适大小的数组，所以基于数组随机访问的bucket等算法思想就无法使用，但当我们离散化之后就可以用一个10^5的数组去存放这些数，因为只有这些个数据有效。

在离散化的时候我们一般要考虑去重问题，可以理解成在同一个位置上存放两次数据，所以不需要给它重新分配下标。

然后说一下怎么去重：

unique函数：

他会把一段连续的数据内的相同元素删掉，并返回指向最后一个不重复元素的下一个地址的迭代器。

unique参数：两个维护范围的迭代器

这样我们就得到的了一个缩减版的数组和一个指向数组有效数据的下一个位置的指针，如果我们用vector的话调用erase函数把剩余的无效数据的部分释放掉就得到了一个无重复数据的容器。

现在我们得到了一个无重复数据的递增的vector，可以正式开始离散化了（离散化也是二分求下标的过程）。

离散化模板：

int find(int x)
{int l = 0, r = alls.size() - 1;while(l < r){int mid = l + r >> 1;if(alls[mid] >= x) r = mid;else l = mid + 1;}return r + 1;
}

解释一下参数：x为想要离散化数组的其中一个数据，返回值为离散化后的相对大小，或者叫新下标（这里是从1开始）。

例题：

这一题用得到知识点：离散化、前缀和、二分。

区间和