1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
例题1：查找x（1）
给定一列数组，在数组中查找数据x，如果x存在于数组中，则输出x的
位置，否则输出-1。
例题分析: 本题采用枚举法，从数组的第一个元素开始逐一比较，查找当前元素是否和x相同， 如果相同，则记录当前元素的位置并退出循环，直至循环结束。方便起见，可以将
3、其他应用
JSOI2018江苏省信息学奥林匹克冬令营
例题9：猴子选大王
例题分析:
有了数组工具，我们可以使用数组来模拟猴子选大王的过程。定义一个含m个元素的数 组monkey来记录猴子的状态。用元素下标代表猴子的编号，元素的值表示猴子的状态：
monkey[k]=0表示第k只猴子仍在圈中；monkey[k]=1则表示第k只猴子已经出圈。
位置的初始值记为-1。这种从头开始，逐一枚举的查找方法称为顺序查找法。
1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
例题2：查找x（2）
给定一列数组，在数组中查找数据x，如果x存在于数组中，则输出x的
个数，否则输出0。
例题分析: 本题和上题的区别在于数组中可能存在多个x，这时候不管有没有找到x，都需要将 数组完整地扫描一遍。初始时，记x的个数s为0，每找到一个x，则s++，扫描完毕
次数 1 2 3 4 5 6 7 8 9 10
猜数
提示
500
小
750
大
625
大
562
大
531
大
516
大
508
大
504
大
502
小
503
大
1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
二分查找
如果待查找的元素是有序的，一般我们采用二分查找法来查找元素。
二分查找又称折半查找，其基本思想是：
1. 将n个元素分成大致相等的两部分，取a[n/2]与x做比较； 2. 如果x=a[n/2],则找到x,算法中止； 3. 如果x<a[n/2],则只要在数组a的左半部分查找x； 4. 如果x>a[n/2],则只要在数组a的右半部分查找x。
//如果left=right,表示没有找到。
//记住：right所在的位置是取不到的！
1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
二分查找的平均查找长度
已知一个有序表为（13 18 24 35 47 50 62 83 90 155 134），当用
二分法查找算法进行元素搜索时，成功的平均查找长度是多少？
3、其他应用
JSOI2018江苏省信息学奥林匹克冬令营
例题8：求1~N之间的质数
输入格式：一个数n（1<n<1000000）
输出格式：以空格隔开的素数 输入样例：10 输出样例：2 3 5 7
例题分析: 判断一个数是否为素数一般用循环结构解决。求范围内的素数可以枚举范围内的每一个
数，判断它是否为素数。还有没有更高效的做法？
1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
例题3：找出第二小的数（NOIP2014提高组初赛）
if (S[1] < S[2]) FirstMin = S[1], SecondMin = S[2]; else FirstMin = S[2], SecondMin = S[1]; 在最坏情况下，该算法需要做
50
3、其他应用
JSOI2018江苏省信息学奥林匹克冬令营
例题8：求1~N之间的质数
算法设计： 1. 初始化数组a的元素值都为0， 假设它们都是素数； 2. a[1]=0，1既不是素数，也不是合数； 3. 循环枚举2~sqrt(n)+1，如果当前的数没有被删除，它就是素数；如果当前数是素 数，则删除该素数的所有<=n的倍数，即令a[i]=1; 4. 循环枚举2~n，输出所有值为零的元素下标。
JSOI2018江苏省信息学奥林匹克冬令营
例题9：猴子选大王
M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，
从第1号开始按顺序1，2，…，N报数，凡报到N的猴子退出到圈外，如 此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。M和N由 键盘输入,打印出最后剩下的那只猴子的编号。
输入样例：8 3 输出样例：7
第二讲 数组应用
目录
JSOI2018江苏省信息学奥林匹克冬令营
1、查找元素
2、数值统计 3、其他应用
1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
查找元素
在一列数组元素中按要求查找元素是数组应用中的基本操作，也是很
多较复杂题的重要组成部分。按照题目要求的不同，查找可以分为各
种不同种类，这里主要解决两类查找问题： 1. 查找确定的元素 2. 查找最大的元素
目录
JSOI2018江苏省信息学奥林匹克冬令营
1、查找元素
2、数据统计 3、其他应用
2、数据统计
JSOI2018江苏省信息学奥林匹克冬令营
数据统计
统计学是一门收集、处理、分析、解释数据并从数据中得出结论
的科学。常见的统计方式包括求总数、求平均数、求中位数、求众数
等。由于参与统计的数据通常比较多，所以数组是统计类题目里不可 或缺的工具。
(2) 求考试成绩平均分，并输出； (3) 枚举学生成绩，输出高于平均分的学生学号和成绩。
2、数据统计
JSOI2018江苏省信息学奥林匹克冬令营
例题5：求众数
所谓众数，就是是一组数据中出现次数最多的数，比如，3 3 4 4 4 5 6 6 8 8 9 这
列数中，众数就是4。有时候，在一组数中有好几个众数。
分析：可以画一个表格模拟查找的过程。
下标 数值
0 13
4
1 18
3
2 24
2
3 35
4
4 47
3
5 50
1
6 62
4
7 83
3
8 90
2
9 10 155 134
4 3
查找
所以，总的查找次数是 1*1+2*2+3*4+4*4=33， 平均查找长度是 33/11。
1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
JSOI2018江苏省信息学奥林匹克冬令营
p=0; for (int i=1; i<=m-1; i++) { while (k<n) { p++; if (p>n) p=1; if (a[p]==0) k++; } a[p]=1; k=0; }
ASL=∑Ki / n = ((1+n)*n/2)/n = (1+n)/2
1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
讨论：猜数
这是一个猜数游戏，一位同学默想一个小于1000的正整数，让另一个
同学去猜，然后给出大或者小的提示，采取什么样的策略才能让猜的
次数尽量少呢？
一般我们会采用二分的策略，假如要猜得的数是503，猜数过程如下：
3、其他应用
JSOI2018江苏省信息学奥林匹克冬令营
例题8：求1~N之间的质数
参考程序段： memset(a, sizeof(a), 0); for (int i=2; i*i<=n; i++) if (a[i]==0) for (int j=2; i*j<=n; j++) a[i*j]=1;
3、其他应用
5. 回到1，在新的区域里查找x。
1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
参考程序段
left=1; right=1000; k=0; while (left<right) { mid=(left+right)/2; k=++k; if (mid==x) break; else if (mid>x) right=mid; else left=mid+1; } cout<<k; //这里采取左闭右开的写法，即右边的数不在范围内
程序采用模拟的方法，开始时设置报数变量k的值为0，当前报数猴子的编号变量p的初 值也置为0，如果当前猴子在圈中，则报数，当报数达到n时,对当前报数的猴子作出圈
处理,即monkey[p]置1，同时k清0，然后进行下一轮报数。报数过程循环m-1次，删
除m-1只猴子后，剩下的那只猴子就是选出的大王。
3、其他应用
目录
JSOI2018江苏省信息学奥林匹克冬令营
1、查找元素
2、数值统计 3、其他应用
3、其他应用
JSOI2018江苏省信息学奥林匹克冬令营
例题6：转换二进制
众所周知，整数的十进制转换成二进制采用的是“除2取余，按权展开，
倒序排列”的方法。现给出一个十进制数，保证它在整数（integer） 范围内，请你将它转换成二进制数。
（
A. 2n
）次比较。
for (i = 3; i <=n; i++) if (S[1] < SecondMin) if (S[1] < FirstMin) SecondMin = FirstMin ，FirstMin = S[1] ; else SecondMin = S[1] ;
B. n-1
C. 2n-3 D. 2n-2
后，输出s的值即可。
1、查找元素
JSOI2018江苏省信息学奥林匹克冬令营
平均查找长度
为确定元素在数组中的位置，关键字和给定值进行比较的比较次数的期望值称为查
找算法在查找成功时的平均查找长度（ASL）。对于含有n个数据元素的查找表，查