用C语言编写顺序查找和二分查找(折半查找)

老师让我们做个实验报告可我们初学不会啊!!!希望大家可以帮个忙!!!要求就会是“同一组数据”分别用二分查找和顺序查找来做 要完整的程序,也就是可以运行的。
实验内容及要求:
该实验要求学生利用已学的查找算法,进行程序设计。主要是顺序查找和二分查找法的程序设计,通过对同一组实验数据的不同方法的查找,比较两种查找方法的时间复杂度
很急希望高手帮忙解决!!!谢谢了!!!!!
要能运行的啊

希望大家帮帮忙 这是我所有的分了啊

顺序查找:在一个已知无序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较,直到找出与给定关键字相同的数为止。复杂度为o(n).

二分查找又称折半查找,它是一种效率较高的查找方法。
【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
【算法思想】首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
【算法复杂度】假设其数组长度为n,其算法复杂度为o(log(n))

#include <stdio.h>

//二分查找:
int search(int a[],int x,int n) //x为要查找的元素,n为数组长度
{
int mid=0;
int low=0;
int high=n;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==x)
{ return mid; }
else if(x<a[mid])
{ high=mid-1; }
else
{ low=high+1; }
}
return -1;
}
//顺序查找:
int search1(int a[],int x,int n) //x为要查找的元素,n为数组长度
{
int i;
for(i=0;i<n;i++)
{
if(a[i]==x)
return i;
}
return -1;
}

int main()
{
int i,a[10],x;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
printf("请输入要查找的元素");
scanf("%d",&x);
if(search(a,x,10)!=-1)printf("查找的元素在数组中的位置为%d.\n",search(a,x,10));
else printf("该元素不在数组中\n");
if(search1(a,x,10)!=-1)printf("查找的元素在数组中的位置为%d.\n",search1(a,x,10));
else printf("该元素不在数组中\n");
return 0;
}
温馨提示:内容为网友见解,仅供参考
第1个回答  2008-11-25
老大,人家叫你答C语言啊,你的都不是C语言,晕,楼主,我觉得你出200分我就帮你解决,你的分太低了。。
第2个回答  推荐于2018-04-13
哎,我就辛苦辛苦了啦。

以下是可以编译运行的代码,在VC6.0下通过。

#include <stdio.h>
#define LENGTH 20

void SequenceSearch(int *fp,int Length);
void Search(int *fp,int length);
void Sort(int *fp,int length);

void main()
{
int count;
int arr[LENGTH];

printf("请输入你的数据的个数:\n");
scanf("%d",&count);
printf("请输入%d个数据\n",count);
for(int i=0;i<count;i++)
{
scanf("%d",&arr[i]);
}

int choise=0;
do
{
printf("1.使用顺序查询.\n2.使用二分查找法查找.\n3.退出\n");
scanf("%d",&choise);

if(choise==1)
SequenceSearch(arr,count);
else if(choise==2)
Search(arr,count);
else if(choise==3)
break;
} while (choise==1||choise==2||choise==3);
}

void SequenceSearch(int *fp,int Length)
{
int data;
printf("开始使用顺序查询.\n请输入你想要查找的数据.\n");
scanf("%d",&data);

for(int i=0;i<Length;i++)
if(fp[i]==data)
{
printf("经过%d次查找,查找到数据%d.\n",i+1,data);
return ;
}

printf("经过%d次查找,未能查找到数据%d.\n",i,data);
}

void Search(int *fp,int length)
{
int data;
printf("开始使用顺序查询.\n请输入你想要查找的数据.\n");
scanf("%d",&data);
printf("由于二分查找法要求数据是有序的,现在开始为数组排序.\n");
Sort(fp,length);
printf("数组现在已经是从小到大排列,下面将开始查找.\n");

int bottom,top,middle;

bottom=0;
top=length;

int i=0;
while (bottom<=top)
{
middle=(bottom+top)/2;
i++;
if(fp[middle]<data)
{
bottom=middle+1;
}
else if(fp[middle]>data)
{
top=middle-1;
}
else
{
printf("经过%d次查找,查找到数据%d.\n",i,data);
return;
}
}
printf("经过%d次查找,未能查找到数据%d.\n",i,data);
}

void Sort(int *fp,int length)
{
printf("现在开始为数组排序,排列结果将是从小到大.\n");

int temp;
for(int i=0;i<length;i++)
for(int j=0;j<length-i-1;j++)
if(fp[j]>fp[j+1])
{
temp=fp[j];
fp[j]=fp[j+1];
fp[j+1]=temp;
}

printf("排序完成!\n下面输出排序后的数组:\n");
for(int k=0;k<length;k++)
{
printf("%5d",fp[k]);
}
printf("\n");

}

我粗略的测试了下,没有什么问题,有问题的话可以百度给我留言,当然,程序很容易,你可以自己修改。本回答被提问者和网友采纳
第3个回答  2008-11-25
/*顺序查找:*/
#include<stdio.h>
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int i,x,y;
printf("输入你要查找的数:\n");
scanf("%d",&x);
y=0; //标记是否已找到,y=1表是找到了,y=0表示没找到
for(i=0;i<10;i++) //循环,把x和数组中的元素一个个比较
{
if(x==a[i]) //如果x=a[i]说明已经找到
{
y=1; //把y变成1,说明已经找到了
printf("你要查找的数%d在第个%d位置\n",x,i+1); //输出找到的相关信息
break; //跳出循环
}
}
if(y==0)printf("无法找到你要查找的数\n"); //y=0表示找不到
}

/*二分查找: 添个主函数调用下就好了*/
int search(int a[],int x,int n)
{
int mid=0;
int low=0;
int high=n;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==x)
{ return mid; }
else if(x<a[mid])
{ high=mid-1; }
else
{ low=high+1; }
}
return -1;
}
第4个回答  2008-11-25
我这里有。。。
typedef int ElemType;
//二分法查找
const ElemType* myFind(const ElemType* a,int n,const ElemType& e) {
const ElemType* front=a,*rear=a+n-1,*mid;
while(rear>=front) {
mid=front+(rear-front)/2;
if(e== *mid) return mid;
else if(e>*mid) front=mid+1;
else rear=mid-1;
}
return 0;
}
//递归描述二分法查找
const ElemType* myFind_dg(const ElemType* front,const ElemType* rear,const ElemType& e) {
if(front>rear) return 0;
const ElemType* mid=front+(rear-front)/2;
if(e== *mid) return mid;
else if(e>*mid) return myFind_dg(mid+1,rear,e);
else return myFind_dg(front,mid-1,e);
}

顺序查找,简单我就不说了,一个循环的事。

用C语言编写顺序查找和二分查找(折半查找)
顺序查找:在一个已知无序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较,直到找出与给定关键字相同的数为止。复杂度为o(n).二分查找又称折半查找,它是一种效率较高的查找方法。【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排...

C语言折半查找法详细代码(假如有10个已排好序的数)
折半查找即二分查找,思想是:在一组有序的数据中查找一个数据,首先将要查找的数据与这组数中间的值比较,如果要查找的数据比它小,则在左半部分中继续查找;若比中间值大,则在右半部分中继续查找,相等的话就表示已找到,直接返回。这样,每次查找都可以将查找范围缩小一半,以此达到O(log N)的...

用C语言写二分查找的代码!!!
加上主函数的最后两行调用两次查找函数很多余,代码显得不够简练。建议改成:include <stdio.h>#include <stdlib.h>int Search(int *a, int key){ \/\/ 在顺序表中折半查找 key的数据元素。若找到,则函数值为 int low = 0, mid; \/\/ 该元素的数组下标;否则为0。 int high = 14...

求查找算法(折半查找法,顺序查找法,分别在一个程序里)“动画演示”程序...
折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于...

C语言程序题:写出递归与非递归两种折半查找程序,并分析其时间空间复杂...
折半查找算法描述如下:在有序表中,把待查找数据值与查找范围的中间元素值进行比较,会有三种情况出现:1) 待查找数据值与中间元素值正好相等,则放回中间元素值的索引。2) 待查找数据值比中间元素值小,则以整个查找范围的前半部分作为新的查找范围,执行1),直到找到相等的值。3) 待...

C语言中使用函数实现:数据的输入,排序,输出和查找(要求折半查找...
mid;} int main(){ int a[N],n;input(a,N);\/*输入*\/ isort(a,N);\/*排序*\/ output(a,N);\/*输出*\/ scanf("%d",&n);\/*要查找的元素*\/ printf("%d\\n",binsh(a,n,0,N-1));\/*存在的话打印位置,不存在的话打印-1*\/ return 0;} 有用的话,请楼主及时采纳,谢谢 ...

用C语言编写非递归算法实现折半查找(二分查找)
int* binary_search( int* a, int* b, int n ){ int* m;while ( b > a ) { m = a + ( b - a ) \/ 2;if ( *m < n )a = m + 1;else if ( *m > n )b = m;else return m;} return NULL;} int main(){ int a[] = { 1,3,5,7,9,11,13,15,17,19 }...

c语言先排序后折半查找程序的实验报告
1实验目的:熟练掌握一维数组,二维数组的定义,初始化和输入输出方法;熟练掌握与数组有关的常用算法(如查找,排序等)。2实验内容:设定一个整形数组存放20个元素,用直接赋值的方法在程序中初始化该数组。先对这些无序的数据进行排序,然后采用折半查找,把要寻找的数的位置输出出来。3算法描述流程图 源...

在n个已经排好序从小到大的数中查询某一个数据,如果找到就指出其在n个...
h> int Dichotomy(int a[],int _value,int n){ \/\/ 二分法(也称折半查找法) int index=0; \/\/ 当前数组的首元素下标 int current=n-1; \/\/ 数组当前的大小 int k; \/\/ 当前数组中间的数的下标 while (index<current) { \/\/ 开始二分法查找 k=(index+current)\/2...

C语言中的“折半查找法”是什么?
折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。例如排序后的数据是1 5 12 35 64 78 89 123 456 你要查找12,首先用12跟上面排好顺序的9个数中间那个比较(64),12<64,因此你查找的数据在前半部分,即1 5 12 35...

相似回答