二分演算法無序

① 用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，並退出演算法；若待查序列不為空，則將它的中間元素與目標數值進行比較，判斷是否相等；若相等，則返回中間元素索引，並退出演算法；此時已查找成功。若不相等，則比較中間元素與目標數值的大小。

二分查找的一個技巧是：不要出基升亮現else，而是把所有情況用else，if寫清楚，這樣可以清楚地展現所有細節。本文都會使用else，if，旨在講清楚搏寬，讀者理解後可自行簡化。