ABC146-C問題で二分探索法を理解する - Qiita

目次 1 二分探索とは 2 言語 3 実装 3-1 全探索 3-2 二分探索 4 考察 1 二分探索とは ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。 二分探索は資格試験でも度々登場する非常に有名で基本的なアルゴリズムです。 また、AtCoderなどに参加している方がまず学習すべきアルゴリズムでもあります。 ABCのA問題やB問題では全探索(full search)で解ける問題が多いですが、計算量がO(n)であることから多くの計算が求められる問題になるとACを出すことが難しくなります。 それに対して二分探索は計算量がO(log_2(n))と非常に高速に計算処理を行うことが可能です。