第13回 期末試験対策演習 解答・解説¶
第13回のドリル（全67問）の答えとかんたんな解説です。間違えた問題は、コードを Colab に打ち込んで実行し、動きを確かめてください。
第1部 リストと range の応用（第09回の範囲）¶
（問1〜問17）
問 1 次のプログラムの出力を答えてください。
word = "computer"
print(len(word))
答え 8
len() は文字列にも使える。"computer" は8文字。
問 2 次のプログラムの出力を答えてください。
words = ["cat", "tiger", "lion", "panda"]
c = 0
for i in range(0, len(words)):
if len(words[i]) >= 5:
c = c + 1
print(c)
答え 2
5文字以上は tiger(5) と panda(5) の2つ。cat は3、lion は4文字。
問 3 次のプログラムの出力を答えてください。
word = "success"
c = 0
for i in range(0, len(word)):
if word[i] == "s":
c = c + 1
print(c)
答え 3
s-u-c-c-e-s-s。"s" は先頭と後ろ2つの3個。
問 4 次のプログラムの出力を答えてください。
a = [9, 4, 6, 2, 7]
print(a[-1])
答え 7
a[-1] は末尾の要素。7。
問 5 次のプログラムの出力を答えてください。
a = [5, 1, 8, 3]
print(a[-3])
答え 1
後ろから3番目。a[-3] は a[1] と同じで 1。
問 6 次のプログラムの出力を答えてください。
c = 0
for i in range(0, 9, 2):
c = c + 1
print(c)
答え 5
range(0, 9, 2) は 0, 2, 4, 6, 8 の5個（9 は含まない）。
問 7 次のプログラムは、1 から 9 までの奇数（1、3、5、7、9）を1行ずつ出力します。空欄【？】に入るものを選んでください。
for i in range(1, 10, 【？】):
print(i)
- (0)
3 - (1)
1 - (2)
2 - (3)
9 - (4)
0
答え （2）
21 から 2 ずつ進めると奇数だけになる。range の3つ目の引数はステップ。
問 8 次のプログラムの出力を答えてください。
for i in range(6, 2, -1):
x = i
print(x)
答え 3
range(6, 2, -1) は 6, 5, 4, 3（2 は含まない）。最後の i は 3。
問 9 次のプログラムは、10 から 1 までの整数を大きい順に1行ずつ出力します。空欄【？】に入るものを選んでください。
for i in range(10, 【？】, -1):
print(i)
- (0)
1 - (1)
0 - (2)
-1 - (3)
11 - (4)
10
答え （1）
0逆順の range も「終わりの値は含まない」。1 まで出すには終わりに 0 を指定する。
問 10 次のフローチャートの出力を答えてください。
答え 9
range(4, 1, -1) は 4, 3, 2（1 は含まない）。s = 4 + 3 + 2 = 9。
問 11 次のフローチャートは、3 + 2 + 1 を計算して 6 と出力します。空欄（破線の箱）に入るものを選んでください。
- (0)
s = s + i - (1)
s = i - (2)
s = s + 1 - (3)
print(s) - (4)
s = 0
答え （0）
s = s + iループのたびに i を s に足し込む。s = s + i が「合計をためる」の基本形。
問 12 for i in range(3, 10, 3): の i が取る値の並びとして正しいものを選んでください。
- (0)
3, 6, 9 - (1)
0, 3, 6, 9 - (2)
3, 4, 5 - (3)
3, 6, 9, 12 - (4) エラーになる
答え （0）
3, 6, 93 から 3 ずつ進み、10 の手前まで。3, 6, 9（次の 12 は 10 以上なので出ない）。
問 13 次のプログラムの出力を答えてください。
x = 4
y = 9
tmp = x
x = y
y = tmp
print(y)
答え 4
tmp 経由の入れ替え（swap）。y には元の x の 4 が入る。
問 14 次のプログラムは、x と y の値を入れ替えて 8 3 と出力します。空欄【？】に入るものを選んでください。
x = 3
y = 8
tmp = 【？】
x = y
y = tmp
print(x, y)
- (0)
y - (1)
x - (2)
tmp - (3)
0 - (4)
x + y
答え （1）
x消えてしまう前に、元の x を tmp に取っておく。取っておくのは x。
問 15 次のプログラムの出力を答えてください。
a = [6, 2, 9]
tmp = a[0]
a[0] = a[2]
a[2] = tmp
print(a[0])
答え 9
a[0] と a[2] を入れ替える。入れ替え後の a[0] は元の a[2] = 9。
問 16 次のプログラムの出力を答えてください。
a = [3, 5, 2, 4]
for i in range(0, len(a) - 1):
if a[i] > a[i + 1]:
tmp = a[i]
a[i] = a[i + 1]
a[i + 1] = tmp
print(a[1])
答え 2
隣同士の1パス。[3,5,2,4]→[3,2,5,4]→[3,2,4,5]。a[1] は 2。
問 17 次のプログラムの出力を答えてください。
fruits = ["apple", "kiwi", "melon"]
print(len(fruits[2]))
答え 5
fruits[2] は "melon"。その文字数は 5。
第2部 2重ループ（第10回の範囲）¶
（問18〜問33）
問 18 次のプログラムの出力を答えてください。
c = 0
for i in range(0, 3):
for j in range(0, 3):
c = c + 1
print(c)
答え 9
外側3回 × 内側3回 = 9回。
問 19 次のプログラムの出力を答えてください。
c = 0
for i in range(0, 2):
for j in range(0, 3):
c = c + 1
print(c)
答え 6
外側2回 × 内側3回 = 6回。
問 20 次のプログラムの出力を答えてください。
for i in range(1, 3):
for j in range(1, 4):
x = i * j
print(x)
答え 6
最後に実行されるのは i=2, j=3 のとき。x = 2 * 3 = 6。
問 21 次のプログラムで c = c + 1 が実行される回数を選んでください。
c = 0
for i in range(0, 4):
for j in range(0, 2):
c = c + 1
- (0)
4 - (1)
2 - (2)
6 - (3)
8 - (4)
16
答え （3）
8外側4回 × 内側2回 = 8回。足し算（4 + 2 = 6）ではなく掛け算。
問 22 次のプログラムの出力を答えてください。
numbers1 = [1, 3]
numbers2 = [0, 2]
total = 0
for i in range(0, len(numbers1)):
for j in range(0, len(numbers2)):
total = total + numbers1[i] * numbers2[j]
print(total)
答え 8
全組み合わせの積の合計。10 + 12 + 30 + 32 = 0 + 2 + 0 + 6 = 8。
問 23 次のプログラムの出力を答えてください。
line = ""
for i in range(0, 3):
for j in range(0, 2):
line = line + "*"
print(len(line))
答え 6
line を作り直していないので "*" が 3×2 = 6個たまる。
問 24 次のプログラムは、* の三角形（1行目 *、2行目 **、3行目 ***、4行目 ****）を出力します。空欄【？】に入るものを選んでください。
for i in range(0, 4):
line = ""
for j in range(0, 【？】):
line = line + "*"
print(line)
- (0)
i - (1)
i + 1 - (2)
4 - (3)
j - (4)
i - 1
答え （1）
i + 1i = 0, 1, 2, 3 のとき 1, 2, 3, 4 個にするには i + 1。
問 25 次のプログラムの出力の4行目として正しいものを選んでください。
for i in range(0, 2):
for j in range(0, 3):
print(i, j)
- (0)
0 2 - (1)
1 0 - (2)
1 1 - (3)
0 1 - (4)
1 2
答え （1）
1 0出力順は 0 0 / 0 1 / 0 2 / 1 0 / …。4行目で外側が1進み、内側は最初に戻る。
問 26 次のプログラムの出力を答えてください。
c = 0
for i in range(0, 3):
for j in range(0, 3):
if (i + j) % 2 == 0:
c = c + 1
print(c)
答え 5
和が偶数になる組は (0,0)(0,2)(1,1)(2,0)(2,2) の5つ。
問 27 次のプログラムの出力を答えてください。
numbers = [1, 4, 2, 6]
c = 0
for i in range(0, len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] * numbers[j] >= 8:
c = c + 1
print(c)
答え 3
重複のないペアで積が8以上は (4,2)=8、(4,6)=24、(2,6)=12 の3つ。
問 28 次のプログラムは、リストから2つ選ぶ重複のないペア（i < j の組）を 1 2 / 1 3 / 2 3 の3行で出力します。空欄【？】に入るものを選んでください。
numbers = [1, 2, 3]
for i in range(0, len(numbers)):
for j in range(【？】, len(numbers)):
print(numbers[i], numbers[j])
- (0)
0 - (1)
i - (2)
i + 1 - (3)
1 - (4)
j
答え （2）
i + 1内側を i + 1 から始めると、同じ要素や逆向きのペアを避けられる（i < j の組だけになる）。
問 29 次のプログラムの出力を答えてください。
c = 0
for i in range(0, 4):
for j in range(0, i):
c = c + 1
print(c)
答え 6
内側の回数は i = 0, 1, 2, 3 のとき 0, 1, 2, 3 回。0 + 1 + 2 + 3 = 6。
問 30 長方形や三角形を1行ずつ表示するとき、line = "" を外側ループの中（各行のはじめ）に書くのはなぜですか。
- (0) 行ごとに line を空に作り直すため
- (1) プログラムを速くするため
- (2) エラーを防ぐため
- (3) line を数値にするため
- (4) 内側ループの回数を変えるため
答え （0） 行ごとに line を空に作り直すため
作り直さないと前の行の記号が残り、行がどんどん長くなってしまう。
問 31 次のプログラムの出力を答えてください。
c = 0
for i in range(0, 4):
for j in range(0, 4):
if i == j:
c = c + 1
print(c)
答え 4
i == j になるのは (0,0)(1,1)(2,2)(3,3) の4回。
問 32 次のプログラムの出力を答えてください。
colors = ["red", "blue"]
sizes = ["S", "M", "L"]
c = 0
for i in range(0, len(colors)):
for j in range(0, len(sizes)):
if len(colors[i]) == 4:
c = c + 1
print(c)
答え 3
4文字は "blue" だけ。blue と各サイズの組み合わせで 3回。
問 33 次のプログラムの出力を答えてください。
c = 0
for i in range(1, 5):
for j in range(1, 5):
if i * j == 6:
c = c + 1
print(c)
答え 2
i * j = 6 になる組は (2,3) と (3,2) の2つ（1×6 の 6 は範囲外）。
第3部 整列アルゴリズム（第11回の範囲）¶
（問34〜問50）
問 34 次のプログラムの出力を答えてください。
numbers = [7, 3, 9, 1, 6]
min_index = 0
for j in range(1, len(numbers)):
if numbers[j] < numbers[min_index]:
min_index = j
print(min_index)
答え 3
最小値 1 の位置はインデックス 3。
問 35 次のプログラムの出力を答えてください。
numbers = [9, 2, 8, 5]
max_index = 0
for j in range(1, len(numbers)):
if numbers[j] > numbers[max_index]:
max_index = j
print(max_index)
答え 0
最大値 9 は先頭にある。一度も更新されず max_index は 0 のまま。
問 36 次のプログラムは、リストの中の最小値の位置（インデックス）を出力します。空欄【？】に入るものを選んでください。
numbers = [4, 1, 5, 2]
min_index = 0
for j in range(1, len(numbers)):
if numbers[j] 【？】 numbers[min_index]:
min_index = j
print(min_index)
- (0)
> - (1)
== - (2)
< - (3)
!= - (4)
+
答え （2）
<今の候補より小さい値が見つかったら更新する。最小値を探すので不等号は <。
問 37 次のプログラムの出力を答えてください。
numbers = [2, 3, 1]
n = len(numbers)
for i in range(0, n - 1):
for j in range(0, n - 1 - i):
if numbers[j] > numbers[j + 1]:
tmp = numbers[j]
numbers[j] = numbers[j + 1]
numbers[j + 1] = tmp
print(numbers[0])
答え 1
バブルソートで [1, 2, 3] になる。先頭は 1。
問 38 次のプログラムの出力を答えてください。
numbers = [4, 1, 3, 2]
n = len(numbers)
c = 0
for i in range(0, n - 1):
for j in range(0, n - 1 - i):
c = c + 1
if numbers[j] > numbers[j + 1]:
tmp = numbers[j]
numbers[j] = numbers[j + 1]
numbers[j + 1] = tmp
print(c)
答え 6
比較回数はパスごとに 3, 2, 1 回で合計 6回（リストの中身にはよらない）。
問 39 次のプログラムの出力を答えてください。
numbers = [1, 3, 2, 4]
n = len(numbers)
c = 0
for i in range(0, n - 1):
for j in range(0, n - 1 - i):
if numbers[j] > numbers[j + 1]:
tmp = numbers[j]
numbers[j] = numbers[j + 1]
numbers[j + 1] = tmp
c = c + 1
print(c)
答え 1
c は if の中なので交換回数。交換は (3,2) の1回だけ。
問 40 次のプログラムは、バブルソートでリストを小さい順に整列し、[1, 2, 3] と出力します。空欄【？】に入るものを選んでください。
numbers = [3, 1, 2]
n = len(numbers)
for i in range(0, n - 1):
for j in range(0, n - 1 - i):
if numbers[j] > numbers[j + 1]:
tmp = numbers[j]
numbers[j] = numbers[j + 1]
numbers[j + 1] = 【？】
print(numbers)
- (0)
tmp - (1)
numbers[j] - (2)
numbers[j + 1] - (3)
j - (4)
0
答え （0）
tmp交換の3行目。numbers[j] はすでに上書きされているので、tmp に取っておいた元の値を入れる。
問 41 次のフローチャートの出力を答えてください。
答え 5
最小値を探す流れ。m は 8 → 5（9 では更新されない）。5 を出力。
問 42 次のフローチャートは、リストの最小値を探して 4 と出力します。空欄（破線のひし形）に入る条件を選んでください。
- (0)
numbers[j] > m - (1)
numbers[j] < m - (2)
m < numbers[j] - (3)
numbers[j] == m - (4)
j < m
答え （1）
numbers[j] < m今の候補 m より小さい値が見つかったら更新する。最小値なので numbers[j] < m。
問 43 小さい順（昇順）の選択ソートを、大きい順（降順）に変える方法として正しいものを選んでください。
- (0) 内側の比較の
<を>に変える（最小値ではなく最大値を選ぶ） - (1)
tmpを使わずに入れ替える - (2) 外側ループを
range(0, n)に変える - (3) 交換を内側ループの中に移す
- (4) 何も変えなくてよい
答え （0） 内側の比較の
<を>に変える（最小値ではなく最大値を選ぶ）並ぶ向きを決めているのは「何を選んで前に置くか」。最大値を選べば降順になる。
問 44 次のプログラムの出力を答えてください。
numbers = [4, 1, 6]
n = len(numbers)
for i in range(0, n - 1):
for j in range(0, n - 1 - i):
if numbers[j] < numbers[j + 1]:
tmp = numbers[j]
numbers[j] = numbers[j + 1]
numbers[j + 1] = tmp
print(numbers[0])
答え 6
比較が < なので降順に並ぶ。[6, 4, 1] の先頭は 6。
問 45 次のプログラムは、バブルソートでリストを大きい順（降順）に整列し、[6, 4, 1] と出力します。空欄【？】に入るものを選んでください。
numbers = [4, 1, 6]
n = len(numbers)
for i in range(0, n - 1):
for j in range(0, n - 1 - i):
if numbers[j] 【？】 numbers[j + 1]:
tmp = numbers[j]
numbers[j] = numbers[j + 1]
numbers[j + 1] = tmp
print(numbers)
- (0)
> - (1)
< - (2)
== - (3)
!= - (4)
+
答え （1）
<降順は「左が右より小さいとき入れ替える」。比較の不等号を < にする。
問 46 次のプログラムの出力を答えてください。
numbers = [5, 3, 6, 2]
n = len(numbers)
for i in range(0, n - 1):
min_index = i
for j in range(i + 1, n):
if numbers[j] < numbers[min_index]:
min_index = j
tmp = numbers[i]
numbers[i] = numbers[min_index]
numbers[min_index] = tmp
print(numbers[1])
答え 3
選択ソートで [2, 3, 5, 6] になる。numbers[1] は 3。
問 47 次のプログラムの出力を答えてください。
numbers = [6, 4, 5, 2, 3]
min_index = 0
for j in range(1, len(numbers)):
if numbers[j] < numbers[min_index]:
min_index = j
tmp = numbers[0]
numbers[0] = numbers[min_index]
numbers[min_index] = tmp
print(numbers[3])
答え 6
選択ソートの最初の1手。最小値 2（位置3）と先頭を交換して [2,4,5,6,3]。numbers[3] は 6。
問 48 要素数4のリストをバブルソート（効率化版。内側は range(0, n - 1 - i)）で整列するとき、比較が行われる回数を選んでください。
- (0)
3 - (1)
4 - (2)
6 - (3)
12 - (4)
16
答え （2）
6パスごとに 3, 2, 1 回で合計 6回。パスのたびに調べる範囲が1つ縮む。
問 49 次のプログラムは、選択ソートでリストを小さい順に整列し、[1, 2, 3] と出力します。空欄【？】に入るものを選んでください。
numbers = [1, 3, 2]
n = len(numbers)
for i in range(0, n - 1):
min_index = 【？】
for j in range(i + 1, n):
if numbers[j] < numbers[min_index]:
min_index = j
tmp = numbers[i]
numbers[i] = numbers[min_index]
numbers[min_index] = tmp
print(numbers)
- (0)
i - (1)
0 - (2)
j - (3)
1 - (4)
n
答え （0）
i「まだ並べていない範囲の先頭 i」を最小値の仮の位置にしてから探し始める。
問 50 バブルソートで比較回数 compare_count を数えるとき、compare_count = compare_count + 1 を置く場所として正しいものを選んでください。
- (0) 内側ループの中、if の直前（if の外）
- (1) if の中（交換と同じ場所）
- (2) 内側ループの外
- (3) for より前（プログラムの先頭）
- (4) print の直後
答え （0） 内側ループの中、if の直前（if の外）
比較は if を通るたびに毎回起きる。if の中に書くと交換回数になってしまう。
第4部 探索アルゴリズム（第12回の範囲）¶
（問51〜問67）
問 51 次のプログラムの出力を答えてください。
numbers = [6, 2, 9]
target = 2
flg = 0
for j in range(0, len(numbers)):
if numbers[j] == target:
flg = 1
print(flg)
答え 1
線形探索（あるかないか）。2 は見つかるので flg は 1。
問 52 次のプログラムの出力を答えてください。
numbers = [4, 7, 5]
target = 8
flg = 0
for j in range(0, len(numbers)):
if numbers[j] == target:
flg = 1
print(flg)
答え 0
8 はリストに無いので flg は 0 のまま。
問 53 次のプログラムは、target がリストにあれば 1、なければ 0 を出力します（ここでは 1 になります）。空欄【？】に入るものを選んでください。
numbers = [5, 3, 8]
target = 8
flg = 0
for j in range(0, len(numbers)):
if numbers[j] == target:
【？】
print(flg)
- (0)
flg = 1 - (1)
flg = 0 - (2)
flg = j - (3)
flg = flg - (4)
print(flg)
答え （0）
flg = 1見つかったら flg を 1 にする（見つからなければ 0 のまま）。あるかないかの合図が flg。
問 54 次のプログラムの出力を答えてください。
numbers = [3, 6, 3, 8]
target = 3
pos = -1
for j in range(0, len(numbers)):
if numbers[j] == target:
pos = j
print(pos)
答え 2
ガードが無いので最後に見つかった位置で上書きされる。3 は位置0と2にあり、pos は 2。
問 55 次のプログラムの出力を答えてください。
numbers = [3, 6, 3, 8]
target = 3
pos = -1
for j in range(0, len(numbers)):
if pos == -1 and numbers[j] == target:
pos = j
print(pos)
答え 0
pos == -1 のガードがあると最初に見つかった位置だけを記録する。pos は 0。
問 56 次のプログラムは、target が最初に見つかった位置だけを記録し、1 と出力します。空欄【？】に入るものを選んでください。
numbers = [7, 4, 9, 4]
target = 4
pos = -1
for j in range(0, len(numbers)):
if 【？】 and numbers[j] == target:
pos = j
print(pos)
- (0)
pos == -1 - (1)
flg == 1 - (2)
j == 0 - (3)
pos == j - (4)
numbers[j] == 4
答え （0）
pos == -1pos == -1（まだ見つけていない）をガードにすると、2回目の一致で上書きされない。
問 57 次のプログラムの出力を答えてください。
numbers = [8, 3, 6]
target = 3
pos = -1
c = 0
for j in range(0, len(numbers)):
if pos == -1:
c = c + 1
if numbers[j] == target:
pos = j
print(c)
答え 2
見つかるまでの比較回数。j=0, 1 の2回目で見つかり、j=2 はガードで比較しない。
問 58 次のフローチャートの出力を答えてください。
答え 2
リストの中の 4 を数える流れ。位置0と1の2つ。
問 59 次のフローチャートは、リストの中の 4 の個数を数えて 2 と出力します。空欄（破線の箱）に入るものを選んでください。
- (0)
c = 1 - (1)
c = j - (2)
c = c + 1 - (3)
print(c) - (4)
c = c + 4
答え （2）
c = c + 14 が見つかるたびに個数 c を1増やす。c = c + 1 が「数える」の基本形。
問 60 整列されていないリストに二分探索をそのまま使うとどうなりますか。
- (0) 目的の値があっても見つけられないことがある
- (1) 必ずエラーで止まる
- (2) 正しく動くが遅くなる
- (3) リストが自動で整列される
- (4) 必ず -1 になる
答え （0） 目的の値があっても見つけられないことがある
「真ん中と比べて半分を捨てる」は整列が前提。整列されていないと捨てた側に目的の値が残りうる。
問 61 次のプログラムの出力を答えてください。
numbers = [2, 4, 6, 8, 10, 12, 14]
target = 6
n = len(numbers)
low = 0
high = n - 1
pos = -1
for k in range(0, n):
if low <= high:
mid = (low + high) // 2
if numbers[mid] == target:
pos = mid
low = high + 1
elif numbers[mid] < target:
low = mid + 1
else:
high = mid - 1
print(pos)
答え 2
二分探索。mid=3（8>6）→ high=2、mid=1（4<6）→ low=2、mid=2 で発見。pos は 2。
問 62 次のプログラムの出力を答えてください。
numbers = [1, 3, 5, 7, 9, 11, 13]
target = 13
n = len(numbers)
low = 0
high = n - 1
pos = -1
c = 0
for k in range(0, n):
if low <= high:
c = c + 1
mid = (low + high) // 2
if numbers[mid] == target:
pos = mid
low = high + 1
elif numbers[mid] < target:
low = mid + 1
else:
high = mid - 1
print(c)
答え 3
mid は 3 → 5 → 6 の3回で右端の 13 に届く。7個でも3回。
問 63 次のプログラムの出力として正しいものを選んでください。
numbers = [1, 3, 5, 7]
target = 4
n = len(numbers)
low = 0
high = n - 1
pos = -1
for k in range(0, n):
if low <= high:
mid = (low + high) // 2
if numbers[mid] == target:
pos = mid
low = high + 1
elif numbers[mid] < target:
low = mid + 1
else:
high = mid - 1
print(pos)
- (0)
-1 - (1)
0 - (2)
3 - (3)
4 - (4) エラーになる
答え （0）
-14 はリストに無い。範囲が空（low > high）になり、pos は -1 のまま。
問 64 次のプログラムは、二分探索で target の位置を探して 5 と出力します。空欄【？】に入るものを選んでください。
numbers = [1, 3, 5, 7, 9, 11, 13]
target = 11
n = len(numbers)
low = 0
high = n - 1
pos = -1
for k in range(0, n):
if low <= high:
mid = (low + high) // 2
if numbers[mid] == target:
pos = mid
low = high + 1
elif numbers[mid] < target:
【？】 = mid + 1
else:
high = mid - 1
print(pos)
- (0)
low - (1)
high - (2)
mid - (3)
pos - (4)
target
答え （0）
low真ん中が target より小さいときは、左半分を捨てて low を mid + 1 に上げる。
問 65 次のプログラムの出力を答えてください。
numbers = [1, 3, 5, 7, 9]
target = 5
n = len(numbers)
low = 0
high = n - 1
pos = -1
for k in range(0, n):
if low <= high:
mid = (low + high) // 2
if numbers[mid] == target:
pos = mid
low = high + 1
elif numbers[mid] < target:
low = mid + 1
else:
high = mid - 1
print(low)
答え 5
mid=2 で発見し、low = high + 1 = 5 にして範囲を空にする。だから low は 5。
問 66 1000個のリストを線形探索で調べるとき、最悪の場合（目的の値が無い場合）の比較回数を選んでください。
- (0) 約10回
- (1) 1000回
- (2) 500回
- (3) 1回
- (4) 0回
答え （1） 1000回
線形探索は先頭から順に全部調べる。無ければ 1000回比べることになる。
問 67 約100万個の整列済みリストから二分探索で値を探すとき、比較回数はおよそ何回になりますか。
- (0) 約20回
- (1) 約1000回
- (2) 約50万回
- (3) 約100万回
- (4) 約2回
答え （0） 約20回
1回ごとに範囲が半分になる。100万 → 50万 → … → 1 でおよそ20回（2 の 20乗 ≈ 100万）。