benben792的部落格

二分搜尋法

如果我們要搜尋的數列已經排序完成

則可使用二分法來進行搜尋

二分法是先將資料分割成兩部份

再比較鍵值與中間值的大小

如果鍵值小於中間值

可確定要找的資料在前半段的元素

如此分割數次直到找到為止。

優點

程式容易撰寫

缺點

資料必須事先排序。

演算法

int sequential search(int list[],int,n,int key)

{

   int i;

   for(i=0; i < n, i++)

       if (list[i]==key)

           return i+1;

       return(-1)

}

循序搜尋法

從第一個資料項開始依序取出與「目的資料項」相互比較

直到找出所要的元素或所有資料均已找完為止

這種搜尋法稱為「循序搜尋」。

優點

搜尋效率較佳

缺點

搜尋效率較差

演算法

void binsearch(A[],key,low,high)

{

   int mid;

   if(low<=high)

}

   mid=;

   switch compare(key,A[mid])

{

Cace"=": return mid;

Case"<": return binsearch(A,key,low,mid-1);

Case">": return binsearch(A,key,mid+1,high);

}

}

return-1;

}

比較循序搜尋法與二分搜尋法

                                    循序收尋法              二分收尋法

收尋方式                        按照順序尋找           從中間位子開始尋找

資料室先排序                     不需要                        需要

適用時機                         資料量小                     資料量大