HakureiHaruhi
8/19/2018 - 3:22 PM

STL function

rt

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中:

lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,
找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,
找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
/**
 * 头文件:<algorithm>
 * 作用:将数列中第x大的数好排序
 * nth_element(start, start+n, end)
 * 使第n大的元素处在数组第n的位置(数组从0开始
 * 注意:不返回值,除第n大的数其他数不保证排序
 */
 
#include<iostream>
#include<algorithm>

using namespace std; 
int main()
{
	int a[]={1,3,4,5,2,6,8,7,9};

	for(int i=0;i<9;i++)
	   cout<<a[i]<<" ";
	nth_element(a,a+5,a+9);
    cout<<endl<<"输出第五大的数: "<<a[4]<<endl; //注意下标是从0開始计数的 
	return 0;
}