作者：张屏翰，（因作者无法发布，由我代他发布）
一、二分（前提：有序数组）
函数：
lower_bound(begin,end,x,rule=less)
upper_bound(begin,end,x,rule=less)
时间复杂度推导
T(n)=T(n/2)+1
a=f(n)=1,b=2
则n^logb(a)=1=f(n)
∴T(n)=O(log(n))
二、分治
1.定义：
分而治之，将无法解决的问题不断分割下去
2.归并排序(即stable_sort())
时间复杂度：O(nlogn)
3.快排(拓展：快排+堆排+插排=内省排序=sort())
时间复杂度：O(nlogn)，最坏O(n^2)
4.在长度为n(n<=10^7)的序列中求第k小的数：
快排改动一下 or using a function called nth_element (RandomAccessIterator first,RandomAccessIterator nth, RandomAccessIterator last, Compare comp=less);
时间复杂度：O(n)
5 个赞