二分

【双指针】【二分】对于序列\(A=\left \{a_1,a_2,\cdots,a_n \right \}\)，记可重集$S=\left { x|x=|a_i-a_j|(1\le i<j\le n) \right } \(，求\)S\(中第\)k$小的数。

将其转化为二分问题：记当前结果为mid，对所有数对\((a_i,a_j)\)中满足\(|a_i-a_j|\le mid\)计数，使用双指针。根据最终\(mid\)与\(k\)的大小进行二分指针移动。

【二分】对于序列\(A=\left \{a_1,a_2,\cdots,a_n \right \}\)，（\(n\le4*10^6\)）求\(x_{min}\)满足\(x\in\N_+,x\notin A\)

将其转化为二分问题，可知\(x\in[1,4*10^6]\)，故对辅助数组\(d[]\)，仅对此范围内的数\(num\)，记\(d[num]=1\)，再将其转为前缀和\(d'[]\)。对当前结果\(mid\)，若\(d[mid]<mid\)，则说明\(x<mid\)，需下移，否则上移。时间复杂度为\(O(n)\)