2011年12月4日星期日

由一道“二分排序查找”想开去..

 


今天在学习C语言的数据组织和处理时,看到了NOIP2003普及组的一道题,是关于排序和二分查找的。想起上个月复赛时我想用二分却不会的囧事,我决定好好练习二分。于是乎一道脑残题就这样诞生了。

 

 


 

 


【二分排序查找-初级版】

题目描述:

有一组数据和一个数字,找出该数字在该组数据中的位置。(该数字必存在于该组数据中。) 

输入:共两行。

第一行为两整数n,k,表示共有n个数,寻找数字k。

第二行为n个整数a[i]。

输出:一个数字l,表示数字k所在位置。若有多个,输出第一个所在位置。 


 


样例输入1:

10 12

29 59 12 64 23 75 33 84 22 25

样例输出1:

3

样例输入2: 

7 100

394 2945 12 100 5823 100 3

样例输出2:

4

数据范围: 

对于100%的数据,0<n<=100,k<=10000,(a[i]<=10000)。 


 

这道题其实非常简单。由于受思维定势阻挠,我写了一节课的程序还没写完。后来才恍然大悟,其实什么二分,什么排序,统统用不到。

下面给出题解。

 

本题首先输入的是n和k,由此可以想到在输入第二行数时直接每输入读一个数就和k比较一次,并且计数器加1,如果等于k,就直接输出计数器值(即第几个)。

代码如下:

 

[cc lang='c' ]


#include
int a[100];
int main()
{
int n,k;
int i=0;
scanf("%d %d",&n,&k);
int tmp,found;
found=0;
while((i<=n)&&!found)
{
scanf("%d",&tmp);
i++;
if(tmp==k) {printf("%d",i); found=1;}
}
return 0;
}

[/cc]

但是如果本题修改一下,就不一定这么简单了。


修改如下:


 



题目描述:

有一组数据和一个数字,找出该数字在该组数据升序排列中的位置。 

输入:共两行。

第一行为两整数n,k,表示共有n个数,寻找数字k。

第二行为n个整数a[i]。

输出:一个数字l,表示数字k所在位置。若有多个,输出第一个所在位置。 


 

这样很容易想到用排序。排序完成后,用顺序查找或二分查找即可找到。代码如下:

 

[cc lang='c' ]

int main()
{
int n,k;
int i=0;
scanf("%d %d",&n,&k);
for(i=0;i void BubbleSort(int x);
BubbleSort(n);
int l,m,r,flag;
l=0;r=n-1;
flag=0;
while(!flag&&(l<=r))
{
m=(l+r)/2;
if(k==a[m]) flag=1;
else if(k else l=m+1;

}
if(flag) printf("%d\n",m+1);
else printf("Not Found.\n");
return 0;
}
void BubbleSort(int x)
{
int i,j,t;
for(i=0;i for(j=0;j if(a[j]>a[j+1]) {t=a[j];a[j]=a[j+1];a[j+1]=t;};
}
[/cc]
然而此题也可以不用排序和查找。注意到n<=100不算太大,而且数字必存在,那么我们可以直接用一个循环从头开始寻找小于(或大于)此数的数字个数,然后经过简单计算输出答案。在此不再给出代码。

 

如果本题改为”该数字不一定存在于该数组中,若不存在,输出-1“,又会怎样呢?会有多少方法?在此不再阐述,请有兴趣的读者自行分析。