sort函數和lower_bound函數

大理石在哪？劉汝佳：《算法競賽入門經典》p108

題目：

現有N個大理石，每個大理石上寫了一個非負整數。首先把個個數從小到大排序，然後回答Q個問題。

每個問題問是否有一個大理石上寫着某個整數x，如果是還要回答那個大理石上寫着x。

排序後的大理石從左到右編号為1~N。

樣例輸入：

4   1

2    3    5   1

5

5    2

1    3    3    3    1

2    3

樣例輸出：

CASE# 1:

5    found    at    4

CASE# 2:

2    not   found   

3    found     at    3

 分析：略。

代碼：

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=10000;

int main()
{
	int n,q,x,a[maxn],kase=0;
	while(scanf("%d%d",&n,&q)==2&&n)
	{
		cout<<"CASE# :"<<++kase<<endl;
		for(int i=0;i<n;i++)
			cin>>a[i];
		sort(a,a+n);//預設從小到大排序
		while(q--)
		{
			cin>>x;
			int p=lower_bound(a,a+n,x)-a;//查找>=x的第一個位置 
			if(a[p]==x)
				cout<<x<<" found at "<<p+1;
			else
				cout<<x<<" not found"; 
		} 
	}
	return 0;
}
           

結果：

正文：

一、sort函數：對給定區間元素進行排序

        1、預設按照升序排列。

         2、可以修改排序方法，使之從大到小排序。

         3、也可以對按結構體内的元素進行排序。（這個注意下）

#include<iostream>
#include<algorithm>
using namespace std;

struct student
	{
		int grd1;
		int grd2;
	}stu[5]={{5,6},{5,4},{3,8}};

bool comp1(int i,int j)
{
	return i<j;
}

bool comp2(int i,int j)
{
	return i>j;
}

bool comp3(student &x,student &y)//多看兩遍 
{
	if(x.grd1!=y.grd1)
		return (x.grd1>y.grd1);
	if(x.grd2!=y.grd2) 
		return (x.grd2>y.grd2);
}


int main()
{
	int i;
	int a[6]={23,52,12,43,33,29};
	//sort(a,a+6,comp1);
	sort(a,a+6,comp2);
	for(i=0;i<6;i++)
		cout<<a[i]<<" ";
	cout<<endl<<endl;	
		
	

	sort(stu,stu+3,comp3);
	for(i=0;i<3;i++)
	{
		cout<<stu[i].grd1<<" "<<stu[i].grd2<<endl;
	} 
	
	return 0;
} 
           

二、lower_bound函數：在給定區間内查找 大于等于x的第一個位置。（為二分查找）(upper_bound,亦然)

參考文章：

sort:

http://www.cplusplus.com/reference/algorithm/sort/?kw=sort

https://blog.csdn.net/weixin_41112564/article/details/81488307

lower_bound:

http://www.cplusplus.com/reference/algorithm/lower_bound/?kw=lower_bound