欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C语言折半查找

程序员文章站 2024-03-20 18:46:28
...

题目描述

有10个整数已按从小到大的顺序排好序,存储在一个数组中,再输入一个数,要求用折半查找法找出该数是数组中的第几个元素(输出该元素的下标即可)。如果该数不在数组中,则输出"Not exist!"

输入

输入数据共2行

第一行10个整数,按从小到大的顺序输入,中间以空格分隔。

第二行1个整数

输出

折半查找所得该数所在数组中的元素下标,单独占一行。

若该数不存在,则输出一行信息 "Not exist!"

样例输入

1 2 3 4 5 6 7 8 9 10
3

样例输出

2

 

 

提示

 


折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右半部继续搜索x。

C语言第四版教学实验-第六章 数组

#include<stdio.h> 
int main() 
{ 
int n=9,m,i,a[10],j=0,k,s=0; 
for(i=0;i<10;i++) 
scanf("%d",&a[i]); 
scanf("%d",&m); 
while(1) 
{ 
s++; 
k=n; 
n=(n+j)/2; 
if(a[n]==m) 
{
printf("%d\n",n);break; 
} 
else if(a[n]<m) 
j=k;else j=0; 
if(s==11) 
{ 
printf("Not exist!\n"); 
break; 
} 
} 
return 0; 
} 
相关标签: c语言查找