用C语言编写顺序查找和二分查找（折半查找）

Question

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

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

Answer 1

顺序查找：在一个已知无序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止。复杂度为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;
}

Answer 2

老大，人家叫你答C语言啊，你的都不是C语言，晕，楼主，我觉得你出200分我就帮你解决，你的分太低了。。

Answer 3

哎，我就辛苦辛苦了啦。

以下是可以编译运行的代码，在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");

}

我粗略的测试了下，没有什么问题，有问题的话可以百度给我留言，当然，程序很容易，你可以自己修改。本回答被提问者和网友采纳

Answer 4

/*顺序查找：*/
#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;
}

Answer 5

我这里有。。。
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);
}

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