1、STL之排序与检索

例题引入 :

where is the marble-UVA10474

题目大意 :

将输入的一组数正序排序，然后进行查找，如果找得到就返回次序，找不到就返回notfound

知识点 :

algorithm头文件中的sort和lower_bound函数
sort可以对任意对象进行排序，不一定是内置类型。如果希望用sort排序，这个类型必须要定义小于运算符，或者在排序时传入一个小于函数。排序对象可以存在与普通数组里，也可以存在于vector里(sort(v.begin(),v.end()))

sort(a，a+n) // 普通数组
sort(v.begin(),v.end()) // vector、string、

lower_bound作用是查找大于或者等于x的第一个位置

lower_bound(a,a+n,x)-a  // 具体用法图下

关于lower_bound( )和upper_bound( )的常见用法

代码 ：

#include<iostream>
#include<algorithm>
const int maxn = 10000;
using namespace std;
int main(){
 int n,q,x,kase=0;
 while(scanf("%d%d",&n,&q)==2 && n){
  int a[maxn];
  kase++;
  cout << "CASE#" << " " << kase << ':' << endl;
  for(int i = 0;i<n;i++){
   scanf("%d",&a[i]);
  }
  sort(a,a+n);
  while(q--){
   scanf("%d",&x);
   int ans = lower_bound(a,a+n,x)-a;
   if(a[ans]==x){
    printf("%d found at %d\n",x,ans+1);
   }
   else{
    printf("%d not found\n",x);
   }
  }
 }
 return 0;
}