排序查找函数

lower_bound() 时间复杂度为O(n)

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

函数作用

在升序的情况下，返回指向第一个值不小于val的位置，即返回第一个大于等于val值的位置。（通过二分查找）
借助数组实现 从a[0]到a[n]

cout<<a[lower_bound(a,a+n,val)-a];

输出第一个大于或等于val的数

nth_element() 时间复杂度为O(n)

称第 n 个元素为升序序列中”第n大”的元素
例如

2 4 6 8 10

2为第1小 8为第4小

默认升序

void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last);

自定义cmp排序

void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last，
                  Compare cmp);

函数作用

nth_element(a,a+n,a+k);//使第k小整数就位