二分探索

二分探索はデータを持つ配列やリストをあらかじめある大きさを基準にソートしておき効率的に探索する手法です. 配列の真ん中の値を見てそれが探したい値より大きいか小さいかで対象を絞りこんでいきます. 二分探索：手法 1. あらかじめ配列のデータを比較したい値の種類でソートしておく. 2. 候補の真ん中のデータを取り出し、探している値と比べて大きいか小さいかを判定 3. 2.で大きければ真ん中のデータより大きい候補に絞込み、小さければ真ん中のデータより小さい候補に絞込み 4. 3.で絞り込まれた候補に対して再度2.を行い、見つけたいデータになるまで繰り返します. 一度に候補が半分になるため、データが2^n個あった場合はn回でデータを見つけ出すことができます.逆にデータがN個あったするとlog(N)回でデータを見つけ出すということです. そのため、計算量はO(log(N))とわかります.

二分探索は現実で対象のファイルデータを探すときなどでも使えます. ある時点でおかしくなったファイルを探すようなときに 先頭からしらみつぶしに探すのではなく、時系列順でファイルをソートして、見つけたいデータかどうかを効率よく探していくことができます.