输入一个数x,用折半(二分)查找法到一个有序(从大到小)数组中进行查找,并按要求输出。
楼上的:epdc147
其实把递归算法,改成非递归的
//a数组首地址,len为数组长度,x要查找的数,返回值为在数组中的位置, 如果返回-1,表示未找到
int Half(int *a, int len, int x)
{
int head, tail, mid;
head=0;
tail=len-1;
while (head<tail)
{
mid = (tail+head)/2;
if (x < a[mid])
head = ++mid;
else if(x> a[mid])
tail = --mid;
else break;
}
if (x == a[mid]) return mid;
else return -1;
}
#include
int search(int a[],int n,int x);/*对调用的函数进行声明*/
void main()
{
int i,x,z; /*对变量进行定义*/
int a[10];
printf("请输入10个有序的数!
");
for(i=0;i<10;i++)
scanf("%d",&a[i]); /*接收10个有序的数赋值给数组a*/
printf("请输入您要查找的数
");
scanf("%d",&x); /*接收要查找的关键字并赋值给x*/
z=search(a,10,x); /*调用函数search()*/
if(z)
printf("您要查找的数%d在数组中的位置是第%d个元素
",x,z);
else
printf("您要查找的数%d不在数组中!
");
}
int search(int a[],int n,int x) /*被调函数search()*/
{
int low,mid,high;/*定义变量*/
low=0; /*给变量赋初值*/
high=n-1;
while(low<=high) /*折半查找*/
{
mid=(low+high)/2;
if(a[mid]==x)
return mid+1;
else if(a[mid]>x)
high=mid-1;
else low=mid+1;
}
return 0;
}
#include <stdio.h>
main()
{ int a[10]= {18,15,14,12,10,9,6,5,2,1},f,r,m,k=1,x;
printf("请输入要查找的整数x:");
scanf("%d",&x);
f=0;
r=9;
/***********SPACE***********/
while(f<=r&&k)
{ /***********SPACE***********/
m=(f+r)/2;
if(x==a[m]) k=0;
else if(x<a[m])
/***********SPACE***********/
f=m+1;
else
/***********SPACE***********/
r=m-1;
}
/***********SPACE***********/
if(x==a[m])
printf("找到了%d在数组的a[%d]元素中
",x,m);
else
printf("没有找到%d
",x);
}
C++折半查找法
2、查找规则:折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=0,上限为h=4,求中点m=(l+h)\/2,用X与中点元素am比较,若X等于am,即找到,停止查找;否则,若X大于am,替换下限l=m+1...
c语言编程实现“折半查找”的过程。
通过一次比较,将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。但是,折半查找的先决条件是查找表中的数据元素必须有序。参考程序,希望对你有所帮助!include<stdio.h> void main(){ int a[20],x,i,start,end;printf("input 20 numbers:\\n");for(...
已知一有序的序列{1,3,5,7,9},采用折半法分别查找3和6
printf("请输入若干数字(小于99个),以空格间隔,Ctrl+Z键结束:\\n");while(scanf("%d",&a[i])!=EOF) \/\/Ctrl+Z不能使scanf返回EOF,输入的时候按升序排序 { i++;} n=i;printf("请输入要查找的数字:\\n");scanf("%d",&x);for(bot=0;top=n-1;bot<=top)\/\/第一个分号改成...
数据结构题目求答案
3、非空完全二叉树的一个任意结点的右子树深度与其左子树深度的差值或者为0或者为1( y )。4、先序遍历二叉排序树可得到一个关键字有序的序列( n) 。5、在n个结点的无向图,若边数大于n-1,则该图必是连通图 ( n )。6、在n个元素进栈后,它们的出栈顺序和进栈顺序一定正好相反( n ...
折半查找法引申
当解决“结论中含有2”的问题时,折半查找法相当于“分析法”的实际操作。例如,例1是一个典型的例子:例2:已知△ABC,D是BC中点,F在AD上,延长CF交AB于E,证明AF:DF=2AE:BE。通过加倍或折半策略,可以运用中位线定理,将比例关系简化。对于“题设中含有2”的问题,折半查找法则体现了“综合...
折半查找法
折半查找法是效率较高的一种查找方法,假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是:设查找数据的范围下限为l=0,上限为h=4,求中点m=(l+h)\/2,用X与中点元素am比较,若X等于am,即找到,停止查找。否则,若X大于am,替换下限l=m+1,到下半段继续...
...若在输出下标,不在输出“不在”,利用二分法实现?
else if(x>a[m])find1(m+1,r,x);\/\/查找右边 else if(x>n;\/\/输出n待查找数列长度 for(int i=0;i<n;i++)cin>>a[i];\/\/输入n个数 cin>>x;\/\/输入查找值 num=find1(0,n,x);\/\/调用折半查找函数(返回下标)if(num!=-1)\/\/数组下标0~n-1;返回-1查找失败 { cout<<x<<"...
...排序并显示排序结果在此基础上输入一个数用折半法查找该数
Print "排序以后的数是:"For i = 1 To 10 Print a(i);Next i Print x = Val(InputBox("要找的数是:"))i = 1: j = 10 Do m = (i + j) \\ 2 If a(m) = x Then MsgBox (x & " 是第 " & m & " 个数"): Exit Sub Else If x > a(m) Then i = m + 1 ...
C语言:麻烦给程序加个输入一个职工号,用折半查找法找出改职工的姓名的...
unsigned unm; \/*这应该用无符号整型吧!*\/ char sex[15];char old[15];char nation[15];} stud[100];int n=0; \/*职工数*\/ void main(){ int x;meun:while (1){ system ("cls"); \/*清屏*\/ printf ("\\n");printf ("\\t\\t\\t\\t 职工信息管理系统\\n");printf ...
c语言的折半查找法
你的数组的索引为0-14 所以你可以设两个变量 这两个变量a,b是用来限制你要的数的范围的 一开始a=0 b=14 接着取索引为int((a+b)\/2 )的元素与你输入的比较 如果比输入的小的话那么设a=int(a+b)\/2 )接着继续取索引为int((a+b)\/2 )的元素与你输入的比较 如果比输入的大的...
应石复方: 折半查找法是算法一种,可以被任何计算机语言使用.用C语言自然也可以实现. 1、定义: 在计算机科学中,折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在...
叶县13452875564: 二、用折半查找算法查询给定的一个数x是否在int类型数组中,后把数组所有元素输出到文本文件myout.txt. - ?
应石复方: 折半查找用里面的函数bsearch() 函数名: bsearch 功 能: 二分法搜索 用 法: void *bsearch(const void *key, const void *base, size_t nelem, size_t width, int(*fcmp)(const void *, const *)); 语法:#includevoid *bsearch( const void *key, ...
叶县13452875564: 二分查找法的具体算法 - ?
应石复方: 折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务.它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止...
叶县13452875564: 什么是折半查找法 - ?
应石复方: 折半查找法是效率较高的一种查找方法,假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是:设查找数据的范围下限为l=0,上限为h=4,求中点m=(l+h)/2,用X与中点元素am比较,若X等于am,即找到,...
叶县13452875564: 急求计算机简单程序!————二分查找程序、比较排序程序、选择排序!! - ?
应石复方: 二分查找:给你个例子参考下,不是很难的::一个数组包含15个整数元素,已经从小到大排好序,要求输入一个数用折半查找法查找它在数组中的序号#include#includeint Search(int *a,int key) { //在顺序表中折半查找key的数据元素.若找到...
叶县13452875564: 要求输入一个整数,用折半查找法找出该数,若存在,在主函数中输出其所处的位置 - ?
应石复方: #include<stdio.h> void main() { int top=0,bot=14; int c[15]={14,13,12,11,10,9,8,7,6,5,4,3,2,1,0},x;/*数组中的数字可以改变*/ printf("请输入一个数:");scanf("%d",&x); while(top!=bot&&x!=c[(bot+top)/2]){ if(c[(bot+top)/2]<x) bot=(top+bot)/...
叶县13452875564: 写函数,用“折半查找法”查找一个从小到大的顺序排序的整数数组中是否有数x,有返回第几个数,没有返回0. - ?
应石复方: 错多了:1. if(m=1)应该是if(m==1)2. if(m=0)应该是if(m==0)3. p=prime(b[10],t);应该是p=prime(b,t);4. 折半法逻辑也有错误!
叶县13452875564: 帮我看一下用折半法在一个已经排好序的数组中,从键盘上输入某数x,查找x是否在数组中的下标 - ?
应石复方: #include void main( ) { int a[10]={1,2,3,4,6,7,9,10,11,15}; int low=1,high=10,mid,x; int i=0; printf("Input search number:"); scanf("%d", &x ); while(low { mid=(low+high)/2; if(a[mid-1]==x){ printf("the number's position is %d\n",mid); i=1;break;} ...
叶县13452875564: 用C语言编写非递归算法实现折半查找(二分查找) - ?
应石复方: char a[10][5];//按字典序递增 int search(char *x)//二分查找,返回有序表中大于等于x的元素位置 {int low=0,high=9,mid,t;while(low<=high){mid=(low+high)/2;t=strcmp(a[mid],x);//比较中点位置与xif(t==0) return mid;//相等返回其位置elseif(t...
叶县13452875564: C语言折半法查找输入的数 - ?
应石复方: 这是因为前面的输入:scanf("%d",&n); 读取数字时,输入的回车没有被读走,仍留在键盘缓冲区中,所以,scanf("%c%c",&c,&c); 第一次读到的就是这个'\n'即回车符,第二次再读一次才能读到y或n