基本情報技術者 一問一答｜B 第199問

解説

二分探索は整列済み配列の中央の要素と比較し、探索範囲を半分に絞り込む手法である。{10,20,30,40,50,60,70}（添字1〜7）でtarget=50を探すと、①low=1、high=7で中央mid=(1+7)÷2=4、data[4]=40<50なのでlow=5に更新、②low=5、high=7でmid=6、data[6]=60>50なのでhigh=5に更新、③low=5、high=5でmid=5、data[5]=50と一致しfound=trueとなる。よって「見つかる」が正解である。50は配列内に実在するため「見つからない」は誤りであり、整列済み配列への正常な探索なのでエラーや不明にもならない。頻出ポイントは①前提条件としてデータが整列済みであること、②比較のたびに範囲が半減し最大比較回数が約log2(n)回になること、③範囲更新がlow=mid+1またはhigh=mid−1となる境界処理、の3点である。