Ⅰ 用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);
}
}