csp基础知识——分治、查找与排序

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