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

 

今天在学习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;ia[j+1]) {t=a[j];a[j]=a[j+1];a[j+1]=t;};
}
[/cc]

然而此题也可以不用排序和查找。注意到n<=100不算太大,而且数字必存在,那么我们可以直接用一个循环从头开始寻找小于(或大于)此数的数字个数,然后经过简单计算输出答案。在此不再给出代码。
 
如果本题改为”该数字不一定存在于该数组中,若不存在,输出-1“,又会怎样呢?会有多少方法?在此不再阐述,请有兴趣的读者自行分析。

发表评论

电子邮件地址不会被公开。 必填项已用*标注