サンプル問題 [科目B]問13
問13
次の記述中の に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。
関数 search は，引数 data で指定された配列に，引数 target で指定された値が含まれていればその要素番号を返し，含まれていなければ－1を返す。data は昇順に整列されており，値に重複はない。
関数 search には不具合がある。例えば，data の 場合は，無限ループになる。
〔プログラム〕
関数 search は，引数 data で指定された配列に，引数 target で指定された値が含まれていればその要素番号を返し，含まれていなければ－1を返す。data は昇順に整列されており，値に重複はない。
関数 search には不具合がある。例えば，data の 場合は，無限ループになる。
〔プログラム〕
- 要素数が1で，target がその要素の値と等しい
- 要素数が2で，target が data の先頭要素の値と等しい
- 要素数が2で，target が data の末尾要素の値と等しい
- 要素に－1が含まれている
分類
アルゴリズムとプログラミング » データ構造及びアルゴリズム
正解
ウ
解説
関数 search は、昇順で整列されたデータ群から目的のデータを探し、その要素番号を返すプログラムです。本問のプログラムは、2分探索法の実装となります。
2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲を2分の1に狭めることを繰り返して目的のデータを探索するアルゴリズムであり、以下の目的のデータを探します。
解答群それぞれのケースを検討してみると以下のようになります。
2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲を2分の1に狭めることを繰り返して目的のデータを探索するアルゴリズムであり、以下の目的のデータを探します。
- 探索範囲の中央に位置する値と目的値を比較する
- 目的値の方が小さければ中央から探索範囲の最後までを、目的値の方が大きければ探索範囲の最初から中央まで探索範囲から除外する（探索範囲を2分の1にする）。
- 目的値を見つけるまで、①と②を繰り返す
解答群それぞれのケースを検討してみると以下のようになります。
- low = 1、high = 1 の状態でwhile文が開始されます。
middle ← (1 + 1) ÷ 2 の商 = 1
data[1] が目的のデータ（target）と等しいので、その要素番号1を返して終了します。
※data[1] が目的のデータ（target）と等しくない場合は、low または high に1が代入されるので永久ループとなります。 - low = 1、high = 2 の状態でwhile文が開始されます。
middle ← (1 + 2) ÷ 2 の商 = 1
data[1] が目的のデータ（target）と等しいので、その要素番号1を返して終了します。 - 正しい。
low = 1、high = 2 の状態でwhile文が開始されます。
middle ← (1 + 2) ÷ 2 の商 = 1
引数 data は昇順に整列されており、data[1] は目的のデータ（target）よりも小さいので、low に middle の値を代入します（low = 1）。
再度 low = 1、high = 2 の状態で繰り返すことになり、同じ処理が行われます。このように永久ループとなります。 - 要素に－1が含まれているという理由で永久ループになることはありません。