题目详情
用二分法在一个有序数列{1,2,3,4,5,6,7,8,9,10}中查找key值,若找到key则输出其在数组中对应的下标,否则输出not found。
文章目录
一、输入样例
二、输出样例
三、代码展示
四、思路体现
五、难点记录
一、输入样例
直接输入一个要查找的正整数key。
没有其它任何附加字符。
1)第一个输入样例
4
2)第二个输入样例
15
二、输出样例
找到则在一行中按照“weizhi:下标”的格式输出其在数组中对应的下标,否则输出not found。
1)第一个输出样例
weizhi:3
2)第二个输出样例
not found
三、代码展示
#include
int main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10}; //定义初始数组
int i,key,index1,index2,mid; //key:准备查找的值;index1:最小下标;index2:最大下标;mid:中间值下标
scanf("%d",&key); //输入要查找的正整数key
for(index1=0,index2=9;index1<=index2;){ //通过for循环进行查找,
mid=(index1+index2)/2;
if(key==a[mid]){
printf("weizhi:%d",mid); //若是找到key的话,直接break结束循环
break;
}else if(keyindex2)printf("not found");
}
四、思路体现
设n个元素的数组a已升序排列,用index1和index2
两个变量来表示查找的区间,即在a[index1] 〜 a[index2]
区间去查找key。
初始状态为index1=0,index2=n-1
。
首先用要查找的key与查找区间的中间位置元素a[mid]
(mid = (index1 + index2) / 2
)比较,如果相等则找到;如果x < a[mid]
,由于数组是升序排列的,则只要在a[index1] 〜 a[mid-1]
区间继续查找;如果x > a[mid]
,则只要在a[mid+1] 〜 a[index2]
区间继续查找。
也就是根据与中间元素比较的情况产生了新的区间值index1、index2
值,当出现index1 > index2
时,说明不存在值为key的元素。
五、难点记录
不了解二分查找法的特点;
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)