線形探索と二分探索の違い
データの中から目的の値を見つける探索の方法について述べた文として最も適当なものはどれか．
-
1 二分探索は，先頭から順に一つずつ照合していく方法なので，並べ替えをしなくてよい．
誤り．先頭から順に一つずつ照合するのは線形探索の手順である．二分探索は，中央にある値と目的の値を比べて探す範囲を絞る．
-
2 線形探索は，探す範囲を毎回半分に絞るので，データの個数が増えても手数はほぼ変わらない．
誤り．範囲を半分ずつ絞るのは二分探索である．線形探索では，データの個数が増えるほど調べる回数も増える傾向にある．
-
3 二分探索は，大小の順に並んだデータに対して，探す範囲を半分ずつ絞り込んでいく方法である． 正解
正しい．二分探索は，大小の順に並んだデータの中央の値と目的の値を比べ，目的の値がある側だけを残して範囲を半分ずつ絞り込む方法である．あらかじめ大小の順に並んでいることが前提になる代わりに，データが多いときは線形探索より少ない手数で見つけられる．
-
4 線形探索は，データを大小の順に並べ替えてからでないと使うことができない方法である．
誤り．先頭から順に一つずつ調べる線形探索は，データの並び順に関係なく使える．並べ替えが前提となるのは二分探索のほうである．
用語集へ