申論題 - 阿摩線上測驗

申論題資訊

試卷：107年 - 107 調查特種考試_三等_電子科學組：計算機概論#74288
科目：計算機概論
年份：107年
排序：0

二、下圖是二元搜尋法（binary search）的一個示意圖。此例乃在一已排序的陣列 A[0:11]中，找尋一個值為 Target=22 的元素的位置。一開始先令 first←0，last←11。

⑵此例剛好用了三個回合就找到了 Target=22，其位置在 A[6]。請列出其他也剛好會用了三個回合就找到了的所有 Target 值。（5 分）

詳解提供者：Yuan chen

Binary Search 模擬表格

Target	Round	first	last	mid
4	1	0	11	5
	2	0	4	2
	3	0	1	0
7	1	0	11	5
	2	0	4	2
	3	0	1	0
	4	1	1	1
10	1	0	11	5
	2	0	4	2
	3	3	4	3
14	1	0	11	5
	2	0	4	2
	3	3	4	3
	4	4	4	4
36	1	0	11	5
	2	6	11	8
	3	6	7	6
	4	7	7	7
77	1	0	11	5
	2	6	11	8
	3	9	11	10
	4	9	9	9
81	1	0	11	5
	2	6	11	8
	3	9	11	10
91	1	0	11	5
	2	6	11	8
	3	9	11	10
	4	11	11	11

故答案 4,10,81

Target	Round	first	last	mid
4	1	0	11	5
	2	0	4	2
	3	0	1	0
7	1	0	11	5
	2	0	4	2
	3	0	1	0
	4	1	1	1
10	1	0	11	5
	2	0	4	2
	3	3	4	3
14	1	0	11	5
	2	0	4	2
	3	3	4	3
	4	4	4	4
36	1	0	11	5
	2	6	11	8
	3	6	7	6
	4	7	7	7
77	1	0	11	5
	2	6	11	8
	3	9	11	10
	4	9	9	9
81	1	0	11	5
	2	6	11	8
	3	9	11	10
91	1	0	11	5
	2	6	11	8
	3	9	11	10
	4	11	11	11

Target	Round	first	last	mid
4	1	0	11	5
	2	0	4	2
	3	0	1	0
7	1	0	11	5
	2	0	4	2
	3	0	1	0
	4	1	1	1
10	1	0	11	5
	2	0	4	2
	3	3	4	3
14	1	0	11	5
	2	0	4	2
	3	3	4	3
	4	4	4	4
36	1	0	11	5
	2	6	11	8
	3	6	7	6
	4	7	7	7
77	1	0	11	5
	2	6	11	8
	3	9	11	10
	4	9	9	9
81	1	0	11	5
	2	6	11	8
	3	9	11	10
91	1	0	11	5
	2	6	11	8
	3	9	11	10
	4	11	11	11

Target	Round	first	last	mid
4	1	0	11	5
	2	0	4	2
	3	0	1	0
7	1	0	11	5
	2	0	4	2
	3	0	1	0
	4	1	1	1
10	1	0	11	5
	2	0	4	2
	3	3	4	3
14	1	0	11	5
	2	0	4	2
	3	3	4	3
	4	4	4	4
36	1	0	11	5
	2	6	11	8
	3	6	7	6
	4	7	7	7
77	1	0	11	5
	2	6	11	8
	3	9	11	10
	4	9	9	9
81	1	0	11	5
	2	6	11	8
	3	9	11	10
91	1	0	11	5
	2	6	11	8
	3	9	11	10
	4	11	11	11