APCS-程式忍者

2016觀念題③

✭✭✭✩✩

循序搜尋二分搜尋

int f1(int a[], int value) {

int r_value = -1;

int i = 0;

while (i < 100) {

if (a[i] == value) {

r_value = i;

break;

}

i = i + 1;

}

return r_value;

}

int f2(int a[], int value) {

int r_value = -1;

int low = 0, high = 99;

int mid;

while (low <= high) {

mid = (low + high) / 2;

if (a[mid] == value) {

r_value = mid;

break;

} else if (a[mid] < value) {

low = mid + 1;

} else {

high = mid - 1;

}

return r_value;

}

給定一整數陣列 a[0]、 a[1]、 …、 a[99]且 a[k]=3k+1，以 value=100 呼叫以下兩函式，假設函式 f1 及 f2 之 while 迴圈主體分別執行 n1 與 n2 次 (i.e, 計算 if 敘述執行次數，不包含 else if 敘述)，請問 n1 與 n2 之值為何? 註： (low + high)/2 只取整數部分。

(A) n1=33, n2=4

(B) n1=33, n2=5

(D) n1=34, n2=5

解題說明：

這題在比較「循序搜尋」和「二分搜尋」，「3k+1」只是要快速創造出100個排序好的數字，沒有特殊的意義。左邊程式相對的簡單，只是一個一個比對是否正確而已。右邊的程式稍微複雜一點，原理就是控制索引的最小值「low」和最大值「high」來縮小範圍。

i從0開始，一直到 i=33，就會得到 a[i] = 100，從0～33一共是34次。

根據提示，「low」和「high」的變化表列如下，我們可以看到第5次就能得到 a[i] = 100

i	a[i]
0	1
1	4
2	7
...	...
33	100

low	high	mid	a[mid]
0	99	49	148
0	48	24	73
25	48	36	109
25	35	30	91
31	35	33	100

一樣是要找到「100」這個值，用「循序搜尋」要34次，用「二分搜尋」只要5次。如果要找的量增加，這個差距還會更大。但是「循序搜尋」還是有它的優點，就是資料不用排序，程式碼也很簡單易懂，在資料量不大時還是相當有用的。

如果對上述「二分搜尋」的操作方式不清楚，可以參考我們整理出來的簡化範例和圖示如下：

附錄3a. 簡化範例1 給定10個數的陣列 a = [1,4,7,10,13,16,19,22,25,28] ，用二分搜尋找到「10」的演算過程如下：
a[ ]	0	1	2	3	4	5	6	7	8	9
a[mid]	1	4	7	10	13	16	19	22	25	28
1st	⇡				⬆					⇑	a[mid] = 13 大於「10」，所以新的 high = 4 -1 = 3
2nd	⇡	⬆		⇑							a[mid] = 4 小於「10」，所以新的 low = 1 +1 = 2
3rd			⇡⬆	⇑							a[mid] = 7 小於「10」，所以新的 low = 2 +1 = 3
4th				⇡⇑							a[mid] = 3 得到正解

附錄3b. 簡化範例2 給定20個數的陣列 a = [1,4,7,10,13,16,19,22,25,28,...] ，用二分搜尋找到「10」的演算過程如下：
a[ ]	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
a[mid]	1	4	7	10	13	16	19	22	25	28	31	34	37	40	43	46	49	52	55	58
1st	⇡										⬆									⇑	a[mid] = 31 大於「10」，所以新的 high = 10 -1 = 9
2nd	⇡					⬆				⇑											a[mid] = 16 大於「10」，所以新的 high = -1 = 4
3rd	⇡		⬆		⇑																a[mid] = 7 小於「10」，所以新的 low = 2 +1 = 3
4th				⇡⬆	⇑																a[mid] = 3 得到正解

附錄3c. 原始範例給定100個數的陣列 a = [1,4,7,10,13,16,19,22,25,28,...] ，用二分搜尋找到「100」的演算過程如下：
a[ ]	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	...	99
a[mid]	1	4	7	10	13	16	19	22	25	28	31	34	37	40	43	46	49	52	55	58	61	64	67	70	73	76	79	82	85	88	91	94	97	100	103	106	109	112	115	118	121	124	127	130	133	136	139	142	145	148	...	298
1st	⇡																																																	⬆		⇑
2nd	⇡																								⬆																								⇑
3rd																										⇡											⬆												⇑
4th																										⇡					⬆					⇑
5th																																⇡		⬆		⇑