uva 10474 例题5-1

直接用sort 水过。。我在实现查找的时候是采用遍历数组的方式。。书上给出了lower_bound这个函数，百度学习了一下这个函数，，简单来说他就是利用二分查找来实现在有序的数组中查找大于或等于给定数的第一个位置。。返回值也就是大于或等于所要找的数的第一个位置。。于是在书上给出的解法中必须验证返回来的数字是不是跟要找的数相等，如果不等其实就是在该数组中没有要找的这个数。。

接下来是引用一段别人博客里说的关于lower_bound的问题。。链接http://blog.csdn.net/niushuai666/article/details/6734403

函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置

举例如下：

一个数组number序列为：4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标

则

pos = lower_bound( number, number + 8, 3) - number，pos = 0.即number数组的下标为0的位置。

pos = lower_bound( number, number + 8, 9) - number， pos = 1，即number数组的下标为1的位置（即10所在的位置）。

pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。

所以，要记住：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！！~

给出本题的ac代码

#include<cstdio>
#include<algorithm>
using namespace std;
int s[100010];
int main ()
{
	int n,q,kase=0;
	while(scanf("%d%d",&n,&q)==2 && n)
	{
		int i;
		for(i = 0; i < n; i++)
		scanf("%d",&s[i]);
		sort(s,s+n);
		printf("CASE# %d:n",++kase);
		while (q--)
		{
			int x;
			scanf("%d",&x);                    
			for(i = 0; i < n;i++)
			{
				if(x==s[i])
				{
					printf("%d found at %dn",x,i+1);
					break;
				}
			}
			if(i==n) printf("%d not foundn",x);
		}
	}
	return 0;
}

最后

以上就是和谐星月为你收集整理的uva 10474 例题5-1的全部内容，希望文章能够帮你解决uva 10474 例题5-1所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。