例题：
大理石在哪儿
现有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 found3 found at 3
demo:
#include <iostream> #include <algorithm> using namespace std; #define maxn 1000 int main() { int n,q,x,kase = 0; int a[maxn]; while(scanf("%d%d",&n,&q) == 2 && n) { printf("CASE# %d:\n",++kase); for(int i = 0; i < n; i++) { scanf("%d",&a[i]); } sort(a, a + n); while(q--) { scanf("%d",&x); int p = lower_bound(a, a + n, x) - a; if(a[p] == x) { printf("%d found at %d\n", x, p + 1); } else { printf("%d not found\n",x); } } } return 0; } 总结：
1.sort()函数真好使啊。。。
2.lower_bound()函数
资料：
STL中关于二分查找的函数有三个lower_bound 、upper_bound 、binary_search 。这三个函数都运用于有序区间（当然这也是运用二分查找的前提），下面记录一下这两个函数。
ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。
ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于值val的位置。
lower_bound和upper_bound如下图所示：
关于二分法排序，参考下面的博客，讲的太全了。。。
http://blog.csdn.net/EbowTang/article/details/50770315
