Ⅰ 用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;
}
Ⅱ 折半查找为什么必须采用顺序存储结构
折半查找需要先对查找的数据集合排序，并且每次要获得数据列表的中间位置，通过数组这种顺序存储结构，只要一次索引就能获得中间值，如果是链式结构，就每次都要从头遍历到中间位置，耗费大量时间。
Ⅲ 在进行折半查找之前,关键词必须已经有序是对的嘛
折半查找是一种采用顺序存储结构的线性表进行查找的方法，也称为二分查找。在进行折半查找之前，线性表中的数据元素必须按照关键字的值升序或降序排列。
所以在进行折半查找之前,关键词必须已经有序。
请采纳，谢谢。
Ⅳ c语言折半查找 求助大佬
#include <stdio.h>
void sort(int a[],int n)
{
int i,j,t;
for(i=0;i<n-1;++i)
{
for(j=0;j<n-i-1;++j)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
int search(int a[],int n, int s)
{
int i,j;
for(i=0,j=n-1;printf("%5d",(i+j)/2),i<j;)
{
if(a[(i+j)/2]<s)
i=(i+j)/2+1;
else
j=(i+j)/2-1;
}
return a[(i+j)/2]==s?(i+j)/2:-1;
}
int main()
{
int a[10],i,s;
for(i=0;i<10;++i)
scanf("%d",&a[i]);
scanf("%d",&s);
sort(a,10);
for(i=0;i<10;++i)
printf("%5d",a[i]);
printf(" ");
printf(" %s",search(a,10,s)>=0?"Success":"Fail");
return 0;
}
Ⅳ 折半查找的条件是
折半查找的适用条件：
1，有序表，对于无序表，实现需要“预处理”
2，限于顺序存储结构，对于线性链表则无法有效地进行查找等操作。
折半查找是必须针对有序表并且不是线性链表。对于无序表，采用折半查找之前，需要排序，根据采用排序算法的不同，此时整个折半查找的时间复杂度需要考虑排序的时间，而不仅仅是折半查找的
时间复杂度。
Ⅵ 折半查找要求线性表的存储结构为( ),而用顺序查找的线性表既可以采用( ),也可以采用( )
折半查找要求线性表的存储结构为(必须是排好序的(有序 ) ),而用顺序查找的线性表既可以采用(无序 ),也可以采用(有序 )
Ⅶ 折半查找对查找的有序序列有什么要求有什么要求
折半查找必须要求待查找的序列有序。
假设对于递增序列（递减序列反之），mid为序列的中间位置，将序列分成两个部分，折半查找首先会将待查找值 value与序列中间的值 list[mid]进行比较，有三种情况：
value == list[mid]，找到了，直接返回 mid
value > list[mid]，说明待查找值 value可能在右半部分
将 mid改为右半部分的中间值
value < list[mid]，说明待查找值 value可能在左半部分
将 mid改为左半部分的中间值
Ⅷ C++折半查找的基本思想和步骤
折半查找法是效率较高的一种查找方法。
基本思想是：设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；
否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；
如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。
步骤：
1、首先确定整个查找区间的中间位置 mid=（ left + right） /2 。
2、用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功，若大于，则在后（右）半个区域继续进行折半查找，若小于，则在前（左）半个区域继续进行折半查找。
3、对确定的缩小区域再按折半公式，重复上述步骤。最后得到结果：要么查找成功，要么查找失败。折半查找的存储结构采用一维数组存放。
(8)顺序存储结构折半查找扩展阅读
折半查找法的优点：比较次数少，查找速度快，平均性能好；
缺点：是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
Ⅸ 什么是折半查找法
折半查找法是效率较高的一种查找方法，假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是：
设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找。
否则，若X大于am，替换下限l=m+1，到下半段继续查找。
若X小于am，换上限h=m-1，到上半段继续查找，如此重复前面的过程直到找到或者l>h为止。
如果l>h，说明没有此数，打印找不到信息，程序结束。
该方法是查找的范围不断缩小一半，所以查找效率较高。
(9)顺序存储结构折半查找扩展阅读
折半查找法优缺点
Bentley在自己的着作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。
问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。
折半查找法的优点是比较次数少，查找速度快，平均性能好。
其缺点是要求待查表为有序表，且插入删除困难，因此折半查找方法适用于不经常变动而查找频繁的有序列表。
Ⅹ 编程实现顺序查找("哨兵"的使用)与折半查找(有序表)算法.
顺序查找
#include
<stdio.h>
#include
<stdlib.h>
#define
MAX_LENGTH
100typedef
int
KeyType;
typedef
struct
{
KeyType
*elem;
int
length;
}SSTable;
//顺序表的存储结构
int
Search_Seq(SSTable
ST,
KeyType
key){
int
i;
ST.elem[0]
=
key;
//“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必定指向该哨兵
for(i
=
ST.length;
ST.elem[i]
!=
key;
i--)
;
return
i;
//找到的话，则i
!=
0,否则i
=
0
}
void
main()
{
int
i,
key;
SSTable
T;
T.elem
=
(KeyType
*)malloc(sizeof(KeyType));
printf("How
Many
Entries
Do
You
Want
input\n");
scanf("%d",
&T.length);
for(i=1;
i<=T.length;
i++){
printf("Please
input
the
%dth
entries
\n",
i);
scanf("%d",
&T.elem[i]);
}
for
(i=1;
i<=T.length;
i++)
printf("%5d",T.elem[i]);
//显示已经输入的所有数据
printf("\nPlease
input
the
data
you
want
to
search\n");
scanf("%d",
&key);
i
=
Search_Seq(T,key);
printf("the
search
data
is
locate
the
%dth(0
indicate
can
not
find)\n",i);
}
折半查找
#include
<stdio.h>
#include
<stdlib.h>
int
binSearch(const
int
*Array,int
start,int
end,int
key)
{
int
left,right;
int
mid;
left=start;
right=end;
while
(left<=right)
{
mid=(left+right)/2;
if
(key<Array[mid])
{
right=mid-1;
}
else
if(key>Array[mid])
{
left=mid+1;
}
else
return
mid;
}
return
-1;
}
void
main()
{
int
A[]={10,20,30,40,50,60,70,80};
int
n;
printf("Please
search
num:");
scanf("%d",&n);
int
index=binSearch(A,0,8,n);
if(index==-1)
{
printf("no
num");
}
else
{
printf("index=%d",index+1);
}
}