二分探索で探索範囲を更新する

解説

二分探索では、中央の要素 data[mid] と target を比較した後、mid 自体は既に確認済みであるため探索範囲から除外する必要がある。 【data[mid] < target の場合】 target は mid より右側にあるので、low を mid + 1 に更新する。 【data[mid] > target の場合】 target は mid より左側にあるので、high を mid - 1 に更新する。 【トレース例】data = {10, 20, 30, 40, 50}、target = 20 の場合 (1) low=1, high=5, mid=3 → data[3]=30 > 20 → high ← 3-1=2 (2) low=1, high=2, mid=1 → data[1]=10 < 20 → low ← 1+1=2 (3) low=2, high=2, mid=2 → data[2]=20 = 20 → return 2 正しく要素番号 2 が返される。 【見つからない場合の確認】target = 25 の場合 (1) low=1, high=5, mid=3 → data[3]=30 > 25 → high ← 2 (2) low=1, high=2, mid=1 → data[1]=10 < 25 → low ← 2 (3) low=2, high=2, mid=2 → data[2]=20 < 25 → low ← 3 (4) low=3 > high=2 → ループ終了 → return -1 mid を範囲に含めたまま(選択肢イ・ウ・エ)だと、上記のような場合に low = high = mid のまま条件が変わらず無限ループとなる。

選択肢ごとの解説

ア

正解。data[mid] は既に比較済みなので、探索範囲から除外するために low を mid + 1、high を mid - 1 に更新する。

イ

誤り。mid を探索範囲に含めたままにするため、target が配列に存在しない場合に low = mid = high のまま無限ループに陥る。

ウ

誤り。a は正しいが、b で mid を範囲に残すため、target より大きい側を探索する際に無限ループになる場合がある。

エ

誤り。b は正しいが、a で mid を範囲に残すため、target より小さい側を探索する際に無限ループになる場合がある。

オ

誤り。low と high の更新方向を逆にしている。data[mid] < target のとき探索範囲を左へ狭めてしまい、目的の値を見逃す。

カ

誤り。a は正しいが、b で high を mid + 1 にすると探索範囲が広がる方向に更新され、正しく範囲を狭められない。

登録すると解いた結果が残り、間違えた問題は日をおいて復習に出ます。