csp基础知识——分治、查找与排序
分治
分治是一种思想，具体是在解决某类问题的一种解决思路，常常在排序算法中使用。当然用一个具体的例子可以快速了解一下。
假设在一堆（n个）质量相同的真硬币中混入了一枚质量较轻的假硬币，现在要找出来，常规方法是一个一个测量重量，兴许运气好，测几次就能知道结果，运气不好的情况下，可能到最后一个才能知道结果。所以时间复杂度就是O(n)。哦！这种方法实在是太慢了，有没有快一点的方法。那可以分成个数相同的两堆（每堆n/2个，假设是整数），假硬币就在比较轻的那堆里，这样就可以排除一半的硬币，然后我们接着把这堆比较轻的一分为二（每堆n/2/2个），继续找更轻的，就又排除了一些，这样循环往复，直到找到最后两个硬币，测出最轻的那个，即可找到目标。这样的时间复杂度是O(logn)，在基数n比较大的时候，可以大大减少算力和时间复杂度。
好，接下来说一下这样的思路的应用题型。
基础题型：二分查找、归并排序
二分查找
在线性表中要查找某个数值，采用二分查找是个很好的方法，其思路就是分治的思想。二分查找也称折半查找(Binary Search)，它是一种效率较高的查找方法。但是，二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
具体的题目有
1.二分查找元素x在数列中是否存在（求出现位置）
2.二分查找左边界：第一次出现的位置(>=0)
3.二分查找右边界：最后一次出现的位置(<n)
基本方法：
while(l<r){
mid=(l+r)/2;
if(x < a[mid]) r=mid-1;
else if(x > a[mid]) l=mid+1;
else {cout<<mid;//printf("%d",mid);
return 0;//break;
}
}
注意：求mid有多种方法
mid= (l+r)/2 = (l+r)>>1 = l+(r-l)/2 //最后一种可以防止l+r越界
二分函数
1.binary_search(a+begin , a+end , x , cmp);
函数含义：在a数组的下标为[begin,end)区间内，按照cmp的排序规则，找元素x。
找到返回true,找不到返回false。
注意点：
(1)查找区间是左闭右开的：[begin,end),不包含结束位置；
(2)排序规则cmp不是必须的，但查找时的排序规则，必须和排序的规则是一致的；
2.lower_bound() 和upper_bound()
二分查找左边界 T* lower_bound(a+begin , a+end , x , cmp);
函数含义：在a数组的下标为[begin,end)区间内，按照cmp的排序规则，找元素x的左边界（第一个>=元素的x的位置），返回位置指针：
注意点：
(l)基本注意点同binary_search;
(2)此处返回的不是下标的值，而是返回指针：T*p；
(3)如果找不到符合条件的元素位置，指向下标为end的元素位置；
二分查找右边界 T*upper_bound(a+begin , a+end , x , cmp);
函数含义：在a数组的下标为[begin,end)区间内，按照cmp的排序规则，找元素x的右边界（第一个>元素的x的位置），返回位置指针；
注意点：同lower_bound（）