1 搜尋︰
1.1 循序搜尋（線性搜尋）︰
將資料重頭到尾檢查過一遍，即為循序搜尋。
eg.假設有以下十筆資料,欲找數字7
1 2 3 4 5 6 7 8 9 10
=> 由左至右，共需比對7次。
若考慮一般情形的話，循序搜尋N筆資料所須比對的次數最大為N，最小為1，故平均起來需要比對(1+N)/2次。
範例程式
|
int data[10]={1,2,3,4,5,6,7,8,9,10};
//target為要找的資料
int target=7;
//found=0為預設值,若找到則將其設為1
int found=0;
for(int i=0;i<10;i++)
if(target==data[i]){
found=1;
printf("found!at %d position\n",i);
//break可以中斷for迴圈
break;
}
if(found==0)
printf("not found!\n");
|
1.2 二元搜尋 (Binary Search)
二元搜尋法所使用的時機是當資料以經排好順序後，我們先從中間值開始找起。若目標值比中位數來的小，則往小的另一半繼續找；反之則往大的另一邊找。如此尋找的次數便可有效地降低，最多不會超過log2(N)+1次。
eg. 假設有以下10筆資料，欲找數字7，共需比對4次!
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
=>一開始先找中間值5(亦可先找6)，未找到。
| |
|
|
|
|
|
6 |
7 |
8 |
9 |
10 |
=>將範圍縮小成右半邊，再找其中間值8，未找到。 |
|
|
|
|
|
6 |
7 |
|
|
|
=>將範圍縮小成左半邊，再找其中間值6，未找到。 |
|
|
|
|
|
|
7 |
|
|
|
=>將範圍縮小成右半邊，只剩下7，Bingo找到了! |
範例程式
|
int data[10]={1,2,3,4,5,6,7,8,9,10};
//target為要找的資料，found=0為尚未找到，found=1為找到。
int target=7,found=0;
//low為左邊界索引值，high為右邊界索引值，mid為中間值索引值
int low=0,high=9,mid;
//當左邊界小於或等於右邊界 及 尚未找到資料時，重覆執行
while(low <= high && found==0){
mid=(low+high)/2;
if(target==data[mid]){
found=1;
printf("found!at %d position\n",mid);
}
else if(target > data[mid])
low=mid+1;//重設左邊界
else if(target < data[mid])
high=mid-1;//重設右邊界
}
if(found==0)
printf("not found!\n");
|
3 想想看
3.1 若將以上二分搜尋法的程式碼while(low<=high&&found==0)中的low<=high移除，請問執行結果會有何影響?(提示：可分為找到資料與找不到資料兩種狀況來討論)
3.2 請修改以上範例程式碼，使其可以將比對次數印出來。
3.3 想想看：請寫一程式，比較當處理不同的資料數量時(10、100、10000)，線性搜尋與二元搜尋法執行的效率。並請將效率量化。